Statements, Connectives, Truth Tables, Equivalence, Tautologies

statements or propositions

sentences that claim certain things. Can be either true or false, but not both.

Propositional logic

deals with propositions/statements

Propositional constants

T - trueF - False

Atomic propositions

propositional constantspropositional variablesThey cannot be further subdivided: "The sun is shining.

Compound propositions

Not atomic, contain at least one logical connective. "The sun is shining and the sky is blue.








if then→


if and only if<-->

Exclusive or

either . . or but not both"+

And / But Λ

Example:It is hot and sunny.A: It is hot.B. It is sunny.A Λ B

Not ~

Example:It is not hot.~A

Or exclusive

A or B but not bothExample: It is either hot or sunny.(A V B) Λ ~(A Λ B)

Or inclusive

Or VIt is hot or sunny.A V B

Neither. . . nor

~A Λ ~BIt is neither hot nor sunny

Negation Truth Table

P ~PT FF T~P is true if an only if P is false

Conjunction Truth Table

P Q P Λ QT T TT F FF T FF F FP Λ Q is true if an only if both P and Q are true. In all other cases, P Λ Q is false.

Truth Tables

define formally the meaning of logical connectives. Evaluating compound statements: by building their truth tables.

Disjunction (inclusive or)

P Q P V QT T TT F TF T TF F FP V Q is true IFF P is true or Q is true or both are true. P V Q is false IFF both P and Q are false.

Conditional --> Truth Table

P Q P --> QT T TT F FF T TF F TThe implication P --> Q is false IFF P is true however Q is false.In all other cases, the implication is true.

Biconditional <---> Truth Table

P Q P<-->QT T TT F FF T FF F TP <--> Q is true IFF P and Q have same values - both are true or both are false.If P and Q have different values, the biconditional is false.

Exclusive "+" Truth Table

P Q P "+" QT T FT F TF T TF F FP "+" Q is true IFF P and Q have different values. If P and Q have same values, P "+" Q is false.

Logical Equivalence

Two propositional expressions P and Q are logically equivalent if they have the same truth tables. We write P ≡ Q.

Commutative Laws

P V Q ≡ Q V PP Λ Q ≡ Q Λ P

Associative Laws

(P V Q) V R ≡ P V (Q V R)(P Λ Q) Λ R ≡ P Λ (Q Λ R)

Distributive Laws

(P V Q) Λ (P V R) ≡ P V (Q Λ R)(P Λ Q) V (P Λ R) ≡ P Λ (Q V R)

Identity Equivalence

P V F ≡ P, P Λ T ≡ P

Negation Equivalence

P V ~P ≡ T (excluded middle)P Λ ~P ≡ F (contradiction)

Double Negation

~(~P) ≡ P

Idempotent Laws

P V P ≡ PP Λ P ≡ P

De Morgan's Laws

~(P V Q) ≡ ~P Λ ~Q~(P Λ Q) ≡ ~P V ~Q

Universal Bound laws (Domination)

P V T ≡ TP Λ F ≡ F

Absorption Laws

P V (P Λ Q) ≡ PP Λ (P V Q) ≡ P

Negation of T and F

~T ≡ F, ~F ≡ T