Statements (Propositions) Statements are sentences that claim certain things. Can be either true or false, but not both. Propositional logic – deals with propositions Propositional constants: T – true F - false Propositional variables – can have T or F value.

Atomic propositions
:

propositional constants
propositional variables They 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"

Basic logical connectives:
AND, OR, NOT

Connective	pronounced	Symbol in Logic
Negation	NOT	¬, ~
Conjunction	AND	Λ
Disjunction	OR	V
Conditional	if then	→
Biconditional	if and only if	«
Exclusive or	either…or but not both	"+"

Translating from English to symbols

English	Logic	Example
And, but	AND Λ	It is hot and sunny A: It is hot B: It is sunny A Λ B
Not	NOT ¬	It is not hot:

   ¬ A


Or (inclusive)



OR V



It is hot or sunny
A V B



Or (exclusive)



A or B but not both



It is either hot or sunny

(A V B) Λ ¬


(A Λ B)


Neither… nor



¬ A Λ ¬ B



It is neither hot nor sunny

¬ A Λ ¬ B

Truth tables

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

1. Negation (NOT, ~, ¬)




P ~P ------------- T F F T

~P is true if and only if P is false

2. Conjunction (AND, Λ)




P Q P Λ Q ------------------- T T T T F F F T F F F F

P Λ Q is true iff both P and Q are true. In all other cases P Λ Q is false

3. Disjunction (inclusive or) (OR, V)




P Q P V Q ------------------- T T T T F T F T T F F F

P 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

4. Conditional, known also as implication (→)




P Q P → Q ------------------- T T T T F F F T T F F T

The implication P→ Q is false iff P is true however Q is false. In all other cases the implication is true

5. Biconditional (ó )




P Q P « Q ------------------- T T T T F F F T F F F T

Pó 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.

6. Exclusive or ("+")




P Q P "+" Q ------------------- T T F T F T F T T F F F

P"+" Q is true iff P and Q have different values. If P and Q have same values, P"+" Q is false.

Logical equivalence

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

Commutative laws	P V Q ≡ Q V P P Λ 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	P V F ≡ P, P Λ T ≡ P
Negation	P V ~P ≡ T (excluded middle) P Λ ~P ≡ F (contradiction)
Double negation	~(~P) ≡ P
Idempotent laws	P V P ≡ P P Λ P ≡ P
De Morgan's Laws	~(P V Q) ≡ ~P Λ ~Q ~(P Λ Q) ≡ ~P V ~Q
Universal bound laws (Domination)	P V T ≡ T P Λ F ≡ F
Absorption Laws	P V (P Λ Q) ≡ P P Λ (P V Q) ≡ P
Negation of T and F	~T ≡ F, ~F ≡ T

Tautologies and contradictions

Definition: A propositional expression is a tautology if and only if for all possible assignments of truth values to its variables its truth value is T

Example: P V ¬ PIf two expressions P and Q are equivalent, i.e. P ≡ Q, then P « Q is a tautology.
Definition
: A propositional expression is a contradiction if and only if for all possible assignments of truth values to its variables its truth value is F
Example: P Λ ¬ P

Implication

P → QFalse only when P = T and Q = F
True for all other values of P and Q

1. Representing the implication by means of disjunction
P → Q ≡ ¬ P V Q Example: "This textbook can be found in the library or in the bookstore.

P =
The book can be found in the library
Q = The book can be found in the bookstore
Rewrite
P V Q as implication: ~P → Q
If the book is not in the library then it is in the bookstore.

Negation of conditional statements

~(P → Q) = ~( ~ P V Q) = P Λ ~Q Example: This textbook can be found in the library or in the bookstore.
Negation: The book is not in the library and it is not in the bookstore.
Comments:
P → Q means: if P is true then Q is also true.
The negation is: P is true, however Q is false. The negation of a conditional statement is a conjunction, not another if-then statement
Which expressions when negated will result in conditional statements?
Answer: a conjunction. Why? - the negation of a conjunction is a disjunction (De Morgan's laws) Any disjunction is equivalent to if-then statement. Example: The weather is stormy but schools are open. P Λ Q
P: The weather is stormy
Q: Schools are open.
Negation: ~( P Λ Q) = ~P V ~Q = P → ~Q
If the weather is stormy the schools are closed (not open).

Converse, inverse, and contrapositive of P →Q

Converse: Q → P (Change position) Inverse: ~P → ~Q (Change sign) Contrapositive: ~Q → ~P (Change both position and sign) The implication is equivalent to its contrapositive.
The inverse is equivalent to the converse.

Only if and unless

(will not be on the final) The expressions equivalent to P → Q are:

P only if Q
~Q only if ~P
~P unless Q

Syllogisms
(Patterns of arguments , inference rules)

• Modus Ponens and Modus Tollens
Modus ponens (method of affirming)

(1) If P then Q
(2) P
(3) Therefore Q Example:
If it is Sunday we go fishing.
It is Sunday
Therefore we go fishing Modus Tollens (method of denying) (1) If P then Q
(2) ~Q
(3) Therefore ~P Example: If it is Sunday we go fishing
We do not go fishing
Therefore it is not Sunday Modus ponens uses implication, modus tollens uses the contrapositive of the implication.

Examples of invalid arguments
: Inverse error

If it is Sunday we go fishing
It is not Sunday
Therefore we do not go fishing Converse error If it is Sunday we go fishing
We go fishing
Therefore it is Sunday

Disjunctive syllogism

(1) P V Q
(2) ~P
(3) Therefore ~Q Example: During the weekend we either go fishing or we play cards
This weekend we did not go fishing
Therefore, this weekend we were playing cards

Hypothetical syllogism

(1) P → Q
(2) Q → R
(3) Therefore P → R Example: If we win the game we will get much money.
If we have money we will go on a trip to China.
Therefore, if we win the game we will go on a trip to China