Propositional Logic

Let p be a proposition.

The negation of p, denoted by¬† \neg p, is the statement “It is not the case p“.

Example: Let p be It’s cold today, then \neg p = It’s not cold today.

 

Let p and q be propositions. The conjunction of p and q, denoted p \& q, is the proposition “p and q“. This is also written p \land q.

This is true when p and q are true, otherwise false.

Example: Let p be It’s cold today, and q be it’s raining today. p \& q is the proposition it’s cold and it’s raining today. Which is true when it’s cold and raining today, otherwise false (e.g. it’s cold and sunny today).

 

Let p and q be propositions. The disjunction of p and q, denoted p \lor q, is the proposition “p or q“. This is true when either p or q or both are true (i.e. false when both p and q are false).

Example: Let p be It’s cold today, and q be it’s raining today. p \lor q, is the proposition it’s cold today or it’s raining today, which is false only when it’s not cold and it’s not raining today.

 

(There exists an exclusive or \oplus which is true only when only one of p and q are true, false otherwise p \oplus q = p \lor q \& \neg (p \land q.) I. e. the proposition p \oplus q is true when p or q is true and not both p and q are true.)

 

Let p and q be propositions. The conditional statement p \to q is the proposition “if p, then q“. This is false when p is true and q is false, and true otherwise. A true statement cannot lead to a false conclusion. p is the antecedent, q is the consequent.

Example: Let p and q be the propositions it’s cloudy today and it’s raining today. p \to q is if it’s cloudy today, then it’s raining today. This statement is only false when it’s cloudy today, but not raining. It’s true in the other cases: if it’s cloudy today, then it’s raining (today), if it’s not cloudy today, then it’s raining and if it’s not cloudy today, then it’s not raining today. This is more general than the English “if then” construction.

 

Let p and q be propositions. The biconditional statement p \iff q is the proposition “p if and only if q.” This proposition is true when p and q have the same values. This is equivalent to p \to q \& q \to p.

Example: Let p and q be the propositions it’s cloudy today and it’s raining today. p \iff q is true when it’s cloudy and it’s raining today and when it’s not cloudy and it’s not raining today.

This post is heavily influenced by (borrowed from) Discrete Mathematics and its applications, sixth edition. Keneth H. Rosen.

 

 

 

 

 

Advertisements