Proofs Homework

Propositional Logic Semantics

Propositional variables: p, q, r, s, ... (stand for simple sentences)

T: any proposition that is always true

F: any proposition that is always false

Compound propositions: formed from propositional variables and logical operators (all binary except negation):

Negation ¬

Conjunction ∧

Disjunction ∨

Implication →

Biconditional ↔

Exclusive Or ⊕

Truth Tables: assign all possible T, F to all possible variables, and determines all possible T, F of compound propositions; with n variables there are 2n rows in the table

Negation changes T to F and vice versa

Conjunction is only T if both conjuncts are T

Disjunction is only F is both disjuncts are F

Implication is only F is the antecedent is T and the consequent is F

Biconditional is only true if they have the same tvalue

Exclusive Or is only T if they differ in tvalue

Two (compound) propositions are equivalent (≡) iff they always have the same tvalue (see also below)

English translations:

Conjunction: and, but, although, yet, still, ...

Disjunctions: or, unless

Implication: if, if ... then, only if, when, implies, entails, follows from, is sufficient, is necessary, when, whenever

Biconditional: if and only if, just in case, is necessary and sufficient

A set of propositions is consistent iff there is some assignment of tvalue that makes all T

A set of propositions is inconsistent iff there is no assignment of tvalue that makes all T

A tautology is a compound propositions that is always T

A contradiction is a compound propositions that is always F

A contingency is a compound propositions that is sometimes T, sometimes F

A compound proposition is satisfiable iff some assignment of tvalues make it T

A compound proposition is unsatisfiable iff no assignment of tvalues make it T

Two compound propositions p and q are logically equivalent iff p ↔ q is a tautology

Common equivalences:

Predicate and Relational Logic (Quantificational Logic, First Order Logic): Semantics

Variables: x, y, z, ...

Predicates/Relations, Propositional Functions: P(x), M(x), Q(x,y), S(x,y,z), ...

Constants: a, b, c, 0, -1, 4, Socrates, ...

Domain (U): set of things the variables range over

Propositional functions are neither T nor F; however, if all the variables are replaced by constants they become propositions and therefore T or F

Universal Quantifier , “For all x”, symbol: x

Existential Quantifier, “There exists an x”, “For some x”, symbol: x

Some Quantifier Equivalences (DeMorgan’s):

An assertion involving predicates and quantifiers is valid iff it is true: 1) for all domains, and 2) for all propositional functions

An assertion involving predicates and quantifiers is satisfiable iff it is true: 1) for some domains, and 2) for some propositional functions

Proofs: Syntactic Rules

An argument is valid iff it has a valid argument form

An argument form is valid iff it is impossible for the premises to be true and the conclusion false

A argument form is invalid iff it IS possible for the premises to be true and the conclusion false (a counterexample exists)

Inferences rules are simple valid argument forms that can be used to construct more complex arguments.

Each propositional inference rule has associated with it a tautology: the conjunction of the premises implies the conclusion

Proofs

Many proofs involve conditionals: to prove if p, then q, assume p is true and deduce q using the above rules.

A theorem is shown to be true by using: 1) definitions, 2) other theorems, 3) axioms (which are assumed to be true), and 4) the rules of inference.

A lemma is an intermediate theorem proven to aid tin the proof of the final theorem.

A corollary is a theorem that follows quickly from a theorem . A conjecture is a non-theorem that one thinks is true.

A direct proof uses the 4 tools used for proving theorems.

An indirect proof is:

A proof that proves the contrapositive instead, or

A proof by contradiction, which assumes the negation of that to be proved and deduces a contradiction

Disproof by counterexample shows the invalidity of an argument by finding a domain that makes all of the premises true and makes the conclusion (conjecture) false.

Existence proofs prove the existence of an entity with a certain property (usually mathematical)

Uniqueness proofs prove BOTH the existence and uniqueness of an entity with a certain property (usually mathematical): show if there are two with the property, then they are really the same (i.e., suppose there are 2, x and y, and show x=y)

Number Theory

n is an even integer iff there exists an integer k, k ≠ 0, and n=2k

n is an odd integer iff there exists an integer k, such that n=2k+1 or n = 2k-1

4