Logic is an essential tool for rational thought. In this and the next several posts I present the basics of propositional logic, which is the logic of certain kinds of elementary statements. Propositional logic has two main elements:

1. A language for combining simple statements into more complex statements.
2. Rules that tell us when it is logically valid to draw some conclusion from a collection of premises, based only on the logical form of the premises and conclusion.

This post discusses (1), the language of propositional logic.

A proposition is a statement (or claim, or assertion) that is objectively either true or false, although we may not know which. Here are some examples of propositions:

1. \(2 + 3 = 5\).
2. \(5 – 7 = 10\).
3. John F. Kennedy died on December 3, 1916.
4. The Earth’s diameter is less than 10,000 miles.
5. The Greek philosopher Socrates awoke between 6:22 a.m. and 6:41 a.m. local time in Athens on the morning of May 27, 412 B. C. (Gregorian calendar).

Propositions (2) and (3) are known to be false; propositions (1) and (4) are known to be true; and nobody knows whether proposition (5) is true.

The following, however, are not propositions:

1. Johnny is a big kid.
2. You should treat other people the way you would want them to treat you.
3. Braveheart is the best movie of all time.
4. Mary gets angry too quickly.

(1) is simply too vague — is 5 feet 8 inches enough to qualify as “big”? Is 170 pounds large enough? (2) and (4) are value statements, and (3) is an aesthetic judgment; all of these are subjective.

We can combine propositions to make more complex propositions, using logical operators. In describing these operators we will use the variables \(A\) and \(B\) to stand for any two propositions (they may even be the same proposition).  Here are descriptions of the most important logical operators:

Not: \(\neg A\) is the proposition stating that \(A\) is false. For example, \(\neg (\mbox{John’s birthday is in December})\) is the same as the proposition “John’s birthday is not in December.” If \(A\) is true, then \(\neg A\) is false; if \(A\) is false, then \(\neg A\) is true.

And: \(A \wedge B\) is the proposition stating that both \(A\) and \(B\) are true. That is, the proposition \(A \wedge B\) is true if both \(A\) and \(B\) are true, and is false if \(A\) is false or \(B\) is false. Some examples:

• \((\mbox{dogs are mammals}) \wedge (3 – 6 = 4)\) is the proposition stating that both “dogs are mammals” and “\(3 – 6 = 4\)” are true. This particular proposition is false: although “dogs are mammals” is true, “\(3 – 6 = 4\)” is false, and that’s enough to make the combined proposition false.
• \((\mbox{triangles have three sides}) \wedge (\mbox{frogs are amphibians})\) is a proposition that is true, since “triangles have three sides” is true, and “frogs are amphibians” is also true.

Or: \(A \vee B\) is the proposition stating that \(A\) is true or \(B\) is true (possibly both). That is, the proposition \(A \vee B\) is true if at least one of the propositions \(A\), \(B\) are true; it is false only if both of them are false. Some examples:

• \((3 < 10) \vee (3 > 0)\) is true.
• \((9 < 10) \vee (9 > 20)\) is true, since \(9 < 10\) is true.
• \((\mbox{the moon is made of green cheese}) \vee (\mbox{dogs are mammals})\) is true, since “dogs are mammals” is true.
• \((\mbox{Einstein had 3 eyes}) \vee (\mbox{the Earth is 3 miles across})\) is false, since Einstein assuredly did not have three eyes, and the Earth is much more than 3 miles across.

If and only if: \(A \Leftrightarrow B\) is the proposition stating that either both \(A\) and \(B\) are true, or both \(A\) and \(B\) are false. Put another way, \(A \Leftrightarrow B\) says that \(A\) is true if, and only if, \(B\) is true. Some examples:

• \((x=y) \Leftrightarrow (y=x)\) is true for any two numbers \(x\) and \(y\).
• \((\mbox{dogs are mammals} \Leftrightarrow (\mbox{cheese is a food})\) is true, since both “dogs are mammals” and “cheese is a food” are true.
• \((\mbox{triangles have four sides}) \Leftrightarrow (\mbox{2+2=5})\) is true, since both “triangles have four sides” and \(2+2=5\) are false.
• \((\mbox{there are 12 inches to a foot}) \Leftrightarrow (\mbox{3 is a letter of the alphabet})\) is false, since “there are 12 inches to a foot” is true, but “3 is a letter of the alphabet” is false.

If … then: \(A \Rightarrow B\) is the proposition stating that if \(A\) is true, then so is \(B\). That is, \(A \Rightarrow B\) is false only if \(A\) is true but \(B\) is not; it is, by definition, true in all other cases. Some examples:

• \((3 > 5) \Rightarrow (3 > 4)\) is true, since \(3 > 5\) is false.
• \((5 > 3) \Rightarrow (5 > 2)\) is true, since \(5 > 2\) is true.
• \((\mbox{dogs are mammals}) \Rightarrow (\mbox{cats breathe motor oil})\) is false, since “dogs are mammals” is true but “cats breathe motor oil” is false.
• \((\mbox{cats breathe motor oil}) \Rightarrow (\mbox{dogs are mammals})\) is true, since “cats breathe motor oil” is false (also because “dogs are mammals” is true).

Here are some examples of English sentences re-expressed using logical operators:

• “Fred is unemployed”: \[\neg (\mbox{Fred is employed}).\]
• “Susan ate a carrot and a hot dog”: \[(\mbox{Susan ate a carrot}) \wedge (\mbox{Susan ate a hot dog}).\]
• “Todd lives in Orem or Provo”: \[(\mbox{Todd lives in Orem}) \vee (\mbox{Todd lives in Provo}).\]
• “If Mars has life then it must have water”: \[(\mbox{Mars has life}) \Rightarrow (\mbox{Mars has water}). \]
• “My computer turns on only if I jiggle the plug”: \[ (\mbox{My computer turns on}) \Rightarrow (\mbox{I jiggle the plug}).\] There’s a subtlety here: the English statement does not say that jiggling the plug is sufficient for the computer to turn on, but only that it is necessary. That is we cannot have “my computer turns on” being true without “I jiggle the plug” also being true.
• “I will accept the job if you give me a signing bonus; otherwise I won’t”: \[ (\mbox{I will accept the job}) \Leftrightarrow (\mbox{you give me a signing bonus}). \]

To recap, here’s a quick summary of the logical operators:

• \(\neg A\) means “not \(A\),” or, equivalently, “\(A\) is false.”
• \(A \wedge B\) means “both \(A\) and \(B\) are true.”
• \(A \vee B\) means “either \(A\) or \(B\) (or both) is true.”
• \(A \Leftrightarrow B\) means “\(A\) is true if, and only if, \(B\) is true.”
• \(A \Rightarrow B\) means “if \(A\) is true then so is \(B\).”