As the name suggests propositional logic is a branch of mathematical logic which studies the logical relationships between propositions (or statements, sentences, assertions) taken as a whole, and connected via logical connectives.
Propositional logic is also known by the names sentential logic, propositional calculus and sentential calculus. It is useful in a variety of fields, including, but not limited to:
In propositional logic a statement (or proposition) is represented by a symbol (or letter) whose relationship with other statements is defined via a set of symbols (or connectives). The statement is described by its truth value which is either true or false.
A proposition is a statement, taken in its entirety, that is either true or false. For example, a proposition might be:
Unlike syllogistic logic, in propositional logic, this statement is taken in its entirety, usually represented by a symbol, and we only concern ourselves with whether or not it is true or false, not the individual terms in the statement.
In propositional logic, a proposition by convention is represented by a capital letter, typically boldface. For example, the proposition above might be represented by the letter A.
A: All elephants are green.
Each of the propositions is assigned a truth value of either true or false. In other areas (for example computer logic gates) these values are given by the binary representations \(1\) (true) and \(0\) (false).
We say that \(v(P)\) evaluates the proposition \(P\), i.e. returns its truth value.
In propositional logic, the relationships between propositions are represented by connectives.
There are essentially five different connectives outlined in the following table:
| \(\color \textbf\) | \(\color \textbf\) | \(\color \textbf\) |
| Negation | \(\neg\) | NOT |
| Conjugation | \(\wedge\) | AND |
| Disjunction | \(\vee\) | OR |
| Conditional | \(\to\) | If . then |
| Biconditional | \(\leftrightarrow\) | If and only if |
In order to clarify the meaning of a proposition or a connective, a truth table is used.
Truth tables are a way of visualizing the truth values of propositions. A value of true is represented by a "1" and a value of false is represented by a "0".
For example, consider the following propositions:
Proposition C takes on the following truth values:
Represented in a truth table, we have one row for each of the above statements (which include all possible combinations of Marty wearing green boots and/or having a dog), and each column represents the possible states of each of the propositions A, B, and, C above.
So, the four statements above are represented in the following truth table:
| \(A\) | \(B\) | \(C = A \wedge B\) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Connectives are logical symbols which express the relationship between propositions.
There are five basic connectives:
These concepts are further described below.
Negation is a unary logical connective. For any proposition \(P\), the negation of \(P\), denoted \(\neg P,\) is a proposition implying that \(P\) is false. \(\neg P\) is also read as "not" \(P\).
The truth table (1=true, 0=false) for negation is as follows:
| P | \(\neg\) P |
| 1 | 0 |
| 0 | 1 |
For the proposition:
A: The moon is made of green cheese.
What is \(\neg A\)?
The negation of proposition A, would be a statement which is always true if A is false and always false if A is true. The following statement fits that criteria::
\(\neg\) A: The moon is not made of green cheese. \(_\square\)
Logical conjunction is an associative binary logical connective which evaluates as true only if both of the propositions it relates are true.
The truth table for conjugation is as follows:
| P | Q | P \(\wedge\) Q |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
(1 = true, 0 = false)
Consider the following statement:
The elephants are green, and George wears red boots.
What type of proposition is this?
We can assign propositional letters to these statements:
E: Elephants are green
G: George wears red boots.
Then, the above statement is rewritten as:
E \(\wedge\) G
So, this proposition is a conjunction. \(_\square\)
Logical disjunction is an associative binary logical connective which evaluates as true if either of the propositions it relates are true. Note: This is the "inclusive" definition of disjunction, not to be confused with the "exclusive" form equivalent to an "XOR" gate in computer logic.
The truth table for disjunction iis as follows:
| P | Q | P \(\vee\) Q |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
(1 = true, 0 = false)
Consider the following statement:
The elephants are green, or George wears red boots (or both).
Rewrite this using propositional logic.
We can assign propositional letters to these statements:
E: Elephants are green
G: George wears red boots.
Then, the above statement is rewritten as:
E \(\vee\) G \(_\square\)
The logical conditional is the equivalent of the expression "If A then B". The result is true if it is consistent with that statement. The only inconsistent situation is if B is false when A is true. This contradicts the conditional statement. So the definition is as follows:
And this is the corresponding truth table:
| P | Q | P \(\to\) Q |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
(1 = true, 0 = false)
This is a famous problem in the study of deductive reasoning and logic.
You are shown a set of four cards placed on a table, each of which has a number on one side and a colored patch on the other side.
The visible faces of the cards show 3, 8, red and brown.
Which card(s) must you turn over in order to test the truth of the proposition that if a card shows an even number on one face, then its opposite face is red?
A biconditional is a connective that represents the condition "if and only if".
It checks for whether both of the propositions evaluate to the same truth value. It can also be thought of as \( (A \to B)\wedge(B \to A).\)
This is equivalent to the XNOR logic gate.
The truth table looks like this:
| P | Q | P \(\leftrightarrow\) Q |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
(1 = true, 0 = false)
\[\begin A: &\text < The angle is right.>\\ B: &~a^2 + b^2 = c^2. \end \]
Pythagorean theorem states \(A \to B.\)
The converse says \(B \to A.\)Together, we could claim \(A \leftrightarrow B.\)
\[(p \wedge q) \vee (p \wedge q)\] \[(p \implies q) \wedge (q \implies p)\] \[(p \implies q) \vee (q \implies p)\] \[(p \vee q) \implies (p \vee q)\]
What is the logically equivalent proposition of \(\displaystyle
?\)
In summary, here is a truth table showing the functionality of all of the connectives:
| P | Q | \(\neg\) P | P \(\wedge\) Q | P \(\vee\) Q | P \(\to\) Q | P \(\leftrightarrow\) Q |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
So far we have discussed the following simple propositions:
However, we can construct much more complex propositions by combining the above simple propositions to construct an infinite number of combinations of well formed formula, such as:
According to propositional logic, which of the following is not a well formulated formula?
(1): (\(A \wedge B) \to (C \vee D)\)
(2): (\(A \neg B) \to (C \vee D)\)
(3): (\(A \leftrightarrow B) \to (\neg D)\)
A tautology is something that is true just as a matter of logic. An example would be "It is either raining or not raining."
Formally, we say that a proposition is a tautology if it is true for all possible truth assignments of the atomic propositions involved. \(_\square\)
Show that this proposition is a tautology:
\[ ((A \land B) \to C) \leftrightarrow (A \to (B \to C)).\]
We can construct a truth table to verify this:
| \(A\) | \(B\) | \(C\) | \(A \land B\) | \(((A \land B) \to C)\) | \(B \to C\) | \((A \to (B \to C))\) |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
As you can see, columns 5 and 7 contain identical entries for all combinations of A, B, and C. Therefore, \(((A \land B) \to C) \leftrightarrow (A \to (B \to C))\) is indeed a tautology. \(_\square\)
A contradiction is a statement that is false just as a matter of logic. An example would be "It is raining and not raining."
Formally, we say that a proposition is a contradiction if it is false for all possible truth assignments of the atomic propositions involved. \(_\square\)
The negation of a tautology is definitely a contradiction.
Since, as demonstrated above, \(((A \land B) \to C) \leftrightarrow (A \to (B \to C))\) is a tautology, the following is a contradiction:
\[\neg (((A \land B) \to C) \leftrightarrow (A \to (B \to C))). \]
A proposition is contingent if and only if it is neither a contradiction nor a tautology. \(_\square\)
An example of a contingency is
\[ (A \land B) \leftrightarrow (A \vee B).\]
We can see this by constructing the truth table:
| \(A\) | \(B\) | \(A \land B\) | \(A \vee B\) |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
We can see that since the third and fourth columns neither all match, nor all contradict each other, this is an example of a contingency. i.e. Whether or not proposition is valid is contingent upon the values of \(A\) and \(B\).
Contradiction Contingent More than one of these Its not a well formulated formula TautologyAccording to propositional logic is the following a tautology, a contradiction or a contingent?
Two propositions \(A\) and \(B\) are equivalent if and only if \(A \leftrightarrow B\) is a tautology. \(_\square\)
While the biconditional tests whether the two propositions are of equal value for a particular assignment of truth values, the equivalence is the test for all possible truth value assignments.
1 2 3 4 5 This is an unsolved problemHere is a list of several famous logical identities:
In propositional-logic, we have five connectives:
Billy argues that this is too many and that any logical proposition that can be constructed with these five connectives can be constructed with fewer.
What is the fewest number of connectives necessary (including only those listed here) in order to be able to construct any logical proposition that can be constructed with these five?
So far, we have done nothing to distinguish between a good argument and a terrible one.
There are two ways in which an argument can go wrong:
Since, in propositional logic, we cannot do anything to determine whether the premise is actually true, we define the validity of an argument in terms of the second idea.
\( \left \ < P_1, P_2, \cdots, P_n \right \>\) is said to entail \(C\) if and only if there is no truth assignment for which \( P_1, P_2, \cdots, P_n \) are all true and \(C\) is false. \(_\square\)
We denote entailment as follows:
Here is another way to define entailment:
\(\left \ < P_1, P_2, \cdots, P_n \right \>\models C\) if and only if \( ( \left ( P_1 \wedge P_2 \wedge \cdots \wedge P_n \right ) \to C ) \) is a tautology. \(_\square\)
By now, it should be obvious to the reader that an argument is valid if and only if the premise entails the conclusion.
A set of propositions is inconsistent if it cannot be simultaneously all true. Otherwise, it is consistent.
A set of propositions \(\phi = \left \\) is inconsistent if and only if \(\left ( A_1 \wedge A_2 \wedge \cdots \wedge A_n\right )\) is a contradiction.
Otherwise, it is consistent. \(_\square\)
An inconsistent set would be
\[ \phi = \left \. \]
Note that the proposition \(C\) has nothing to do with the inconsistency itself. However, it is a part of an inconsistent set anyway.
Propositional logic is only one of the many formal languages. It is possible that the structure of an argument is lost in converting it from English to propositional logic.
A natural extension to propositional logic is quantified logic, also called predicate logic or first order logic.
