Logic of Compound Statements

The Logic of Compound Statements

Logical Form and Logical Equivalence

An argument is an organization of statements (premises) that entail a conclusion. A valid argument is one that is well organized, an unsound argument may be a valid argument but has poor premises. The following have the same logical/argumentative form but vastly different premises.

• If the bell rings, $p$, or the flag drops, $q$, then the race is over $r$. $\therefore$ If $\neg r$, then neither $p$ nor $q$ occurred.
• If $x=2$, $p$, or $x=-2$, $q$, then $x^2$=4, $r$. $\therefore$ If $\neg r$, then neither $p$ nor $q$ occurred.

Notation and Propositions (Statements)

Propositions are statements that are either true or false: e.g. the sky is blue, (x+1=2 is not) Compound propositions are made of connective proposition statements (e.g. its raining and the sky is blue.)

Name	Symbol	Connection	Meaning
AND (Conjunction)	$\wedge$ (\wedge)	$p\wedge q$	($p\wedge q$) is true if both $p$ and $q$ are true. Otherwise false.
OR (Disjunction)	$\vee$ (\vee)	$p\vee q$	($p\vee q$) is true if either $p$ or $q$ is true (or both) otherwise false.
NOT (Negation)	~ ! $\neg$ (\neg)	$\neg p$	($\neg p$) is true if $p$ is false. And if $p$ is true ($\neg p$) is false.
XOR (Exclusive or)	$\oplus$ (\oplus)	$p\oplus q$	($p\oplus q$) is true if only $p$ is true or if only $q$ is true. (If both $p$ and $q$ are true ($p\oplus q$) is false)
Implication	$\to$	$p\to q$	If $p$ happens then $q$ will happen
Double Implication (Biconditional)	$\leftrightarrow$ (\leftrightarrow)	$p\leftrightarrow q$	$p$ happens if and only if $q$ happens

• Order of operations: $(...)$ then $\neg$ then $\vee =\wedge$
• Tautology is a statement form that is always true. ($p\vee \neg p\equiv T$)
• A contradiction is a statement form that is always false. ($p\wedge \neg p\equiv F$)
• Two statement forms are called logically equivalent if, and only if they have identical truth tables:
• De Morgan’s Law: $\neg (p\wedge q)\equiv (\neg p\vee \neg q)$

Truth Tables

To see all possibilities of a compound proposition, all component propositions are supposed to be true and false. All combinations show all cases in which the compound proposition is true. Take the following truth table as an example:

Since each position of the row has two possible values (true and false) there will be 2 rows for each proposition. Thus, the number of propositions, $n$ causes $2^n$ cases for the compound statements. When dealing with binary, starting with F F F F … = 0 can be useful as each row increments by 1.