Terminology

Question 1

Operator Precedence

Answer 1

Æ
Ę
~
^
v
->

Question 2

Ü

“Fancy U”

Answer 2

Universe of Discourse (allowable choices)

Question 3

Ż

“Fancy Z”

Answer 3

Set of all integers

{…-2, -1, 0, 1, 2,…}

Question 4

M

“Fancy M”

Answer 4

Set of all muffins

Question 5

Ę

“Backwards E”

Answer 5

Existential

“there exists”

Question 6

Æ

“Upside down A”

Answer 6

Universal

“for all”

Question 7

Predicate Calculus (Predicate Logic)

Answer 7

The manipulation of open statements

Question 8

Negation of Quantifiers

Answer 8

DeMorgan’s Law for Quantifiers

~Æx d(x) = Ęx ~d(x)

~Ęx d(x) = Æx ~d(x)

Question 9

Quantifiers

Answer 9

Quantify open statements and make them statements.

Existential and Universal quantifiers

Question 10

Open Statement

Answer 10

Has one or more variables

Is not a statement, but becomes one when the variables are replaced by certain allowable choices (universe of discourse)

p(x): x is an integer

Question 11

Dealing with Nested Quantifiers

Answer 11

Order matters

Read from left to right

Question 12

Bound Variables

Answer 12

Variables with a quantifier applied to it.

Æx ( p(x) -> q(x) )

Question 13

Unbound Variables

Answer 13

Variables with no quantifiers applied

Æx p(x) -> q(x)

Question 14

If p q is a tautology, we can say…

Answer 14

p = q

p is logically equivalent to q

Question 15

is interchangeable with…

Answer 15

Logical equivalence

Question 16

For compound statements p and q, if p -> q is a tautology, we can say…

Answer 16

p logically implies q

p => q

Question 17

Logically Implies

Answer 17

=>

Like logical equivalence but only works in one direction

Question 18

Argument

Answer 18

A series of statements that end in a conclusion.

Can be valid or not.

Question 19

Argument Structure

Answer 19

A bunch of premises conjoined together that lead to a conclusion.

Question 20

An argument is valid…

Answer 20

Iff it is never possible to make the premises true but the conclusion false

Question 21

Rules of Inference

Answer 21

Can only be applied of they match the WHOLE form of each premise they are being applied to.

Yield results in one direction but not necessarily both directions (are logical implications)

Question 22

p
p -> q
________
:. q

Answer 22

(p ^ (p -> q)) -> q

Which is a tautology, so

p ^ (p -> q) => q

*this structure holds for all rules of inference

Question 23

Theorem

Answer 23

A statement that can be shown to be true

Question 24

Proof

Answer 24

A valid argument that establishes the truth of a theorem.

Question 25

Lemma

Answer 25

A less important theorem that is used to prove other results.

Question 26

Axiom

Answer 26

A statement that can be assumed to be true.

These are fundamental building blocks.

Question 27

Conjecture

Answer 27

Something we believe to be true but has not yet been proven.

Question 28

Informal Proof

Answer 28

Multiple rules of interference in one step, steps are skipped, rules or axioms not explicitly stated.

Question 29

Proof by Contraposition

Answer 29

To prove p => q, Start with only ~q and use that to derive ~p.

Negate conclusion, then derive premise.

Question 30

Proof by Contradiction

Answer 30

To show that p=> q, add ~q to our premise and then derive a contradiction.

Question 31

Even

Answer 31

An integer n, is said to be even if there exists some integer k such that n = 2k.

Question 32

Odd

Answer 32

If n is not even, we call it odd, and then there exists some integer k such that n = 2k +1.

Question 33

Closure for the set of all integers.

Answer 33

A set is said to be closed under an operation if that operation takes elements of that set as input and only generates that set as output.

Ż is closed under +, -, *

Ż is not closed under /