Propositional logic is the part of logic that deals with inferences whose logical validity or invalidity depends on the so-called logical connectives. These are words and phrases such as “and”, “or”, “unless”, “except”, “if ..., then ...”, “neither ... nor ...”, etc., which connect sentences into more complex sentences.
When an inference is simple, we can rely on our logical intuition to determine whether it is logically valid or not. For example, everyone would agree that the first inference is logically valid and the second not:
| She can swim, and she can drive a car. | She can swim, or she can drive a car. | |
| She can swim. | She can swim. |
Logical validity or invalidity of an inference depends on its form, not on the content of the sentences it contains. By replacing the non-logical expressions in it with symbols, we make the form to stand out. In the above inferences, this can be done as follows:
| p and q | p or q | |
| p | p |
Obviously, any inference having the first form will be valid, and any inference of the second form will be invalid.
The more complex an inference becomes, the more difficult it is to assess whether it is its logical valid or not. For example, it becomes doubtful whether we can rely only on our logical intuition to determine whether the following inference is valid.
| If this thing is an animal, it either reacts to stimuli or it can move. |
| If this thing does not react to stimuli or cannot move, it is not an animal. |
Substituting “p” for “This thing is an animal”, “q” for “This thing reacts to stimuli”, and “r” for “This thing can move”, we get the following scheme:
| If p, then q or r. |
| If not-q or not-r, then not-p. |
An inference of this form is not logically valid. The conclusion can be false when the premise is true but to be certain of that, we need certain logical techniques that propositional logic offers. Even if we agree that with the help of some reasoning the invalidity of the inference is not so hard to be seen, there are infinitely many more complex inferences for which no one can judge without the use of logical methods whether they are valid or not.
On the other hand, there are inferences that are simple but whose logical validity or invalidity is again a problem for intuition since they are rarely used (if at all) and we are not used to them. Consider, for example, the following inference:
| This arrow is moving and not moving. |
| All pigs can fly. |
The inference is logically valid, but this does not seem obvious. Let us see why it is valid. First, let us explicate its logical form:
| p and not-p |
| q |
The premise is contradictory – it claims that p and its negation not-p are both true. Since q can be any sentence, the validity of the above inference scheme means that any sentence logically follows from a contradiction. In order to prove this, we will assume that the premise is true, i.e. that both p and not-p are true, and will show that then, whatever the sentence q is, it will also be true.
As p is true, “p or q” (where q may be any sentence) will also be true because of this obviously valid inference scheme:
| p |
| p or q |
Since the sentence not-p is true, from it and “p or q” we can infer q by the following obviously valid inference scheme (thus proving what we wanted):
| p or q |
| not-p |
| q |
That anything logically follows from a contradiction is one of the reasons why the law of non-contradiction (one of the most basic laws of logic formulated by Aristotle) must be accepted. When we claim something (hold a view, a thesis, or a theory), we are committed to the truth of certain sentences. This automatically commits us to the truth of the sentences that logically follow from them. If among these sentences there are such that contradict each other, because anything follows from a contradiction, we will have to be committed to the truth of every possible sentence (“Snow is white”, “Snow is not white”, “2+2 = 4”, “2+2 ≠ 4”, ...), which is of course absurd.
This was an example of a logically valid inference which is simple but whose validity is nevertheless not obvious to intuition, because we are not used to such kind of inferences. So, one of the main purposes of logic is to develop general procedures whereby we can check whether an inference is logically valid оr prove that it is such, regardless of its complexity or of whether we are familiar with it.
We will call sentences capable of being true or false propositions or statements. Questions, orders, exclamations, etc. are sentences but they are not propositions (statements) because they are not true or false. Only declarative sentences are statements. (As the only sentences we will be dealing with are statements, we will often say “sentence” instead of “statement” or “proposition”.) The truth or falsehood of a statement is called its truth value. We will say of a true sentence that it has the truth value true, denoting it by “T”, and of a false sentence that it has the truth value false, denoting it by “F”.
Not every declarative sentence is true or false by itself. “I am sick” is true uttered by some person at some time and false uttered by the same person at another time or another person at the same time. “Vienna is far away” is true uttered in New York and false uttered in Budapest. “People have landed on the moon” is true now but it was false before 1960s. So, the truth value of many statements depends on the context – on who utters it, what is the place and time of the utterance, what is meant by the pronouns in it, etc. On the other hand, there are statements, like “The universe is infinite” or “All metals are electrically conductive”, whose truth value is independent of the context. Such sentences are true or false by themselves, which is why they are sometimes called “eternal”. If a statement is of the first type, i.e., if its meaning and truth value depends on the context, we will always imagine that the context is completely determined, i.e., that we know by whom, where and when it was uttered or written, what is meant by the terms, etc. So, these statements will be treated as abbreviations of eternal sentences. For example, if the sentence “Vienna is far away” is uttered in New York, it will be regarded as a shortened version of the sentence “Vienna is far from New York”. If the same sentence is uttered in Budapest, it will be regarded as a shortened version of “Paris is far from Budapest” and thus as different from the first. “I was sick yesterday” uttered by Alice today will be considered a shortened version of the sentence “Alice was sick on [yesterday’s date]” imagining that it is clear who Alice is. This will facilitate our logical work as it will allow us to regard each statement as having a truth value by itself, independently of the context.
Logical words such as “and”, “or”, “if ..., then ...”, “neither ... nor ...” etc. connect sentences into more complex, compound sentences whose truth value depends on the truth values of the constituent sentences. A sentence is atomic if it does not contain other sentences. For example, the compound sentence “The crisis will continue, and taxes will increase” is composed of the atomic sentences “The crisis will continue” and “Taxes will increase” through the logical word “and”. The sentence is true if both atomic sentences are true and is false if either or both are false. The compound sentence “The crisis will continue, or taxes will increase” is true if at least one of the same atomic sentences is true and is false if both are false. The compound sentence “Neither the crisis will continue, nor taxes will increase” is true if the same atomic sentences are both false and is false in all other cases.
By iterative application of such logical words, more and more complex sentences can be formed, whose truth value depends in a definite way on the truth values of the atomic sentences in them. For example, the truth value of the sentence
If the crisis continues and taxes do not increase, either there will be a budget deficit or neither wages will be increased nor there will be Christmas bonuses.
can be uniquely determined by the truth values of the five atomic sentences in it: “The crisis will continue”, “Taxes will increase”, “There will be a budget deficit”, “Wages will be increased”, “There will be Christmas bonuses”. If we know their truth values, we can calculate the truth value of the whole sentence.
Logical words or expressions connecting sentences into more complex sentences so that the truth values of the latter depend entirely on the truth values of the component sentences are called logical connectives. The first logical connective we will introduce is conjunction.
The sentence “The crisis will continue, and taxes will increase” is true if and only if both sentences it contains are true. The same applies to “The crisis will continue but taxes will increase”, “The crisis will continue even though taxes will increase”, “Whereas the crisis will continue, taxes will increase”, and others. Despite the differences in their usage, words or phrases like “and”, “but”, “although”, “even though”, “besides”, “whereas” and others connect two sentences into a new sentence in such a way that the latter is true only if both constituent sentences are true. Such a word or expression is called conjunction in logic. Except the connective itself (“and”, “but”, etc.), “conjunction” is also called the compound sentence thus obtained, i.e. if p and q are two arbitrary sentences, we will call “conjunctions” also the sentences “p and q”, “p but q”, “p although q”, etc. The two constituent sentences in a conjunction are called conjuncts.
The logical connective of conjunction is symbolized by “∧”.1 If “p” represents “The crisis will continue” and “q” “Taxes will increase”, the sentence “The crisis will continue, and taxes will increase” will be symbolized by “p∧q”. We will call the lower-case Latin letters “p”, “q”, “r”, ..., by which we will usually symbolize atomic sentences, propositional letters.
The table below is called truth table. It visualizes the way in which the truth value of a conjunction depends on the truth values of its constituent sentences.
| α | β | α ∧ β |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
α and β stand in the place of arbitrary sentences (atomic or compound). The rows of the table correspond to all possible combinations of truth values of α and β. The first row corresponds to the case in which both sentences α and β are true, the second to the case in which α is true and β is false, etc. In each of these cases, the column under α∧β gives the truth value of the compound sentence. As we know, a conjunction is true if both conjuncts are true (first row) and is false in all other cases (the other three rows).
Unlike the symbolic language of logic, in which it is expressed uniformly with “∧”, in English (and other natural languages) conjunction is expressed in a variety of ways. The simplest is with “and”. “But”, “although”, “however”, etc. express conjunction too, but in addition to the truth values relation shown by the truth table (which is only of interest for logic), these words also point to the contrast between what the constituent sentences express. In “Alice went to the party, but Bob didn’t”, “but” points to the contrast between Alice’s going and Bob’s not-going to the party. “Although”, “even though”, “while”, “however”, “notwithstanding”, “in spite of the fact that”, etc. are used when this contrast is relatively greater. The sentence “In spite of the fact that Alice went to the party, Bob didn’t go” indicates that the speaker thought that if Alice goes to the party, Bob will go too, and is perhaps surprised. “But” stands somewhere between “and” and “even though” or “notwithstanding” in this scale of pointing the contrast. All these differences in usage of words are irrelevant for logic because they do not affect the truth values relation between the whole sentence and its constituents. The conjunction truth table agrees with the usage of all these words or phrases; therefore, usually they all express conjunction.
“And” may expresses conjunction without standing between two sentences. In “Alice and Molly are nice girls”, it is between two proper names. In “Bob got angry and left”, it is between two verbs. In “He handled the task quickly and skillfully”, it is between two adverbs. These sentences should be considered short versions of the following explicit conjunctions, in which “and” stands between sentences: “Alice is a nice girl, and Molly is a nice girl”, “Bob got angry, and Bob left”, “He handled the task quickly, and he handled the task skillfully”.
Sometimes “and” does not express conjunction. For example, unlike “Alice and Molly are nice girls”, the sentence “Alice and Molly are sisters” cannot be rephrased as “Alice is a sister, and Molly is a sister”, as the latter can be true without Alice and Molly being each other’s sisters. The sentence should be considered atomic; so, “and” in it does not express conjunction.
The order of the sentences in a conjunction does not affect its truth value. “It is raining, and it is cold” has the same truth value as “It is cold, and it is raining”. Both sentences are true if and only if their constituent sentences are true (and they are the same). So, “p∧q” always has the same truth value as “q∧p”
Sometimes the order of the sentences in a conjunction indicates an order in time. There is a clear meaning difference between “She took off her shoes and went to bed” and “She went to bed and took off her shoes”. However, this aspect of the usage of “and”, when present, is irrelevant to propositional logic. In these two sentences “and” continues to express conjunction because the compound sentences will be true only if both constituent sentences are true.
Examples of conjunction:
| p ∧ q | p | q |
| Vienna and Budapest are east of Paris. | Vienna is east of Paris. | Budapest is east of Paris. |
| Alice and Molly are married to Bob and George, respectively. | Alice is married to Bob. | Molly is married to George. |
| Both Catholics and Protestants believe in the resurrection. | Catholics believe in the resurrection. | Protestants believe in the resurrection. |
| She’s at home, but she’s sleeping. | She is at home. | She is sleeping. |
| She stayed with him even though he often mistreated her. | She stayed with him. | He often mistreated her. |
| Although it was raining, the concert did take place. | It was raining. | The concert took place. |
| In spite of the fact that he loved her, Bob left Alice. | Bob loved Alice. | Bob left Alice. |
Taking an arbitrary sentence, we can always deny it. Negation is the logical connective that is applied to a sentence to obtain its denial. It is symbolized by “¬”.2 If “p” symbolizes the sentence “Earth is spherical”, “¬p” (pronounced “not-p”) will symbolize the sentence “Earth is not spherical”. As with conjunction, except the logical connective itself (the negative particle “not” in the example), we will call “negation” also the resulting sentence (“Earth is not spherical” in the example). Unlike the other logical connectives, which are applied to two sentences, negation is applied to one sentence.
Below is the truth table of negation showing how the truth value of a sentence with a form of negation depends on the truth value of the initial sentence
| α | ¬α |
| T | F |
| F | T |
If α (an arbitrary sentence) has the value T (true), ¬α has the value F (false), and if α has the value F, ¬α has the value T.
The negation of a natural language (English) sentence cannot always be formed by inserting the negative particle “not”. For example, the negation of “Some cats are black” is not “Some cats are not black”, because both sentences are true, and (as required by the above truth table) a sentence and its negation must always have the opposite truth values. It is “No cats are black”. So, here the negation is obtained by replacing “some” with “no”. The negation of “Alice is sometimes late” is not “Alice is sometimes not late” (both sentences can be true). It is “Alice is never late”. So, here it is obtained by replacing “sometimes” with “never”. A way to form the negation of a sentence that always works is to place the phrase “it is not the case that” or “it is not true that” at the beginning of the sentence. For example, except “Alice is never late”, other variants of the negation of “Alice is sometimes late” are “It is not true that Alice is sometimes late” and “It is not the case that Alice is sometimes late”.
When a natural language sentence is not atomic, often it does not have a main predicate wherein to insert the negative particle “not”. And even if it has such predicate (as is with “Alice and Molly are nice girls”), simply inserting “not” will probably not yield its negation (“Alice and Molly are not nice girls” is not what we are looking for; why?). So, in such cases we are usually forced to use “it is not true that” or “it is not the case that”. For example, the negation of “The crisis will continue and taxes will increase” is
(1) It is not true that the crisis will continue and taxes will increase.
If “The crisis will continue and taxes will increase” (the sentence of which (1) is a negation) is symbolized by “p∧q”, (1) will be symbolized by “¬(p∧q)”. We need the parentheses to indicate that what is negated is the whole conjunction, not just its first member, as is with “¬p∧q”. The last formula corresponds to the sentence “The crisis will not continue, and taxes will increase”. While “¬p∧q” is true only if p is false and q is true, “¬(p∧q)” is true in this and two other cases – if p is true and q is false and if both are false, for then the conjunction becomes false and its negation true.
By itself (1) is ambiguous because “it is not true that”, which corresponds to the connective of negation, may refer to everything which follows (the sentence “the crisis will continue and taxes will increase”), in which case (1) should be symbolized with “¬(p∧q)”, or it may refer only to the first sentence after it (“the crisis will continue”), in which case (1) should be symbolized with “¬p∧q”. As we saw, the two sentences have different meanings. Unlike the symbolic language of logic, natural languages are often ambiguous, and one of the reasons is that they lack parentheses to indicate the scope of logical connectives.
In the language of logic, compound sentences are negated by first enclosing them in parentheses and then putting “¬” in front, as in “¬(p∧q)”. An exception is made when the compound sentence is itself a negation – the negation of “¬p” is “¬¬p”, not “¬(¬p)”. The general rule is that if the negation sign is followed by an opening parenthesis, the scope of the negation is the expression enclosed in the parentheses, and if the negation sign is not followed by an opening parenthesis, its scope is the closest possible sentence (as in “¬p∧q”, where the negated sentence is “p”). We do not need parentheses when the sentence to be negated is itself a negation because in this case the scope of the negation sign is determined by the rule just stated. For example, in “¬¬¬p” the first “¬” can only refer to “¬¬p” as it is the closest possible sentence after it (“¬” and “¬¬” are not sentences); the second “¬” can only refer to “¬p” and the third to “p”.
There is a difference between sentences such as (1) (“It is not true that the crisis will continue and taxes will increase”), in which the whole conjunction is negated (in symbols “¬(p∧q)”), and sentences such as “The crisis will not continue and taxes will not increase”, in which the members of the conjunction are negated. The second sentence may be rephrased with “neither … nor …” – “Neither the crisis will continue, nor the taxes will increase”. “Neither p nor q” is symbolized with “¬p∧¬q”, which has different meaning from “¬(p∧q)”. The former is true only in case both p and q are false, while, except in that case, the latter is also true when one of p and q is true and the other is false. In the way it is meant (as “¬(p∧q)”), (1) (“It is not true that the crisis will continue and taxes will increase”) will be true if the crisis continues and taxes do not increase, while “Neither the crisis will continue, nor taxes will increase” will be false in that case.
Examples of negation:
| ¬p | p |
| Bob is a non-smoker. | Bob is a smoker. |
| No one called. | Someone called. |
| Sometimes Alice doesn’t come on time. | Alice always comes on time. |
| Bob is not home yet. | Bob is already home. |
The word “or” connects two sentences into a more complex sentence in such a way that if one of them is true and the other is false, the compound sentence is true. “The crisis will continue, or taxes will increase” will be true if the crisis continues but taxes are not increased and will also be true if the crisis does not continue but taxes are increased. If both constituent sentences are false (if the crisis does not continue and taxes are not increased, in the example), the or-sentence is false. As for the fourth possible case, when both constituent sentences are true, “or” has two meanings – inclusive and exclusive. The inclusive “or” allows both sentences to be true while the exclusive does not. If in our example “or” is meant inclusively, the sentence will be true if the crisis continues and taxes are increased, but if it is meant exclusively, the sentence will be false. Nothing in the example indicates which sense of “or” is meant. Often, to eliminate this ambiguity, the phrase “or both” or “but not both” is added at the end of or-sentences. In our examples we will always assume that “or” is inclusive.
The logical connective that connects two sentences into a compound sentence the way the inclusive “or” does is called disjunction. It is symbolized with “∨”. Thus, if we symbolize “The crisis will continue” with “p” and “Taxes will increase” with “q”, the sentence “The crisis will continue or taxes will increase” will be symbolized by “p∨q” (pronounced “p or q” or “p disjunction q”). As with “conjunction” and “negation”, we call “disjunction” the logical connective itself (“∨”) as well as the compound sentences obtained by it (e.g., “p∨q” is a disjunction). The two sentences in a disjunction are called disjuncts.
The truth table of disjunction is the following:
| α | β | α ∨ β |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
A sentence with the form of disjunction (α∨β) is false only if its constituents (the sentences α and β) are both false (last row); in all other cases it is true.
As with conjunction, the order of the sentences in a disjunction is irrelevant. “It is raining, or it is cold” always has the same truth value as “It is cold, or it is raining”.
Besides with “or” another way to express a disjunction is with “unless”. Consider the sentence
(2) The crisis will continue unless taxes are reduced.
Let us see how the truth values of this sentence depend on the truth values of the two sentences in it. (2) will be true (nothing refutes it) if the crisis continues and taxes are not reduced. Also, it will be true if the crisis does not continue, and taxes are reduced. These are the two cases in which one of the constituent sentences is true and the other is false, and they are in accordance with the second and the third row of the disjunction truth table above. If both sentences are false, i.e., if the crisis does not continue and taxes are not reduced, (2) will be obviously false. This agrees with the table last row. In the last possible case, when both sentences are true, the situation is exactly as with “or” – there is an ambiguity depending on what the speaker means. Hence, from a logical perspective “p unless q” behaves exactly like “p or q”, which is why in its inclusive sense it also expresses a disjunction.
As was with conjunction, so with disjunction we must distinguish between whether the whole disjunction or only its first member is negated. If we want to deny the sentence “The crisis will continue or taxes will increase”, we may do it with the sentence
(3) It is not true that the crisis will continue or taxes will increase.
Тhe symbolic representation of (3) then will be “¬(p∨q)”. The parentheses show that the whole disjunction is negated. “¬(p∨q)” is true only if p and q are both false, because only then “p∨q” is false and so its negation is true. Due to the lack of parentheses, (3) is ambiguous, since we could also interpret it as “¬p∨q” (“The crisis will not continue, or taxes will increase”). In contrast to “¬(p∨q)”, which is true only if p and q are false, “¬p∨q” is also true if q is true (no matter what the truth value of p is).
Here is another example of a sentence that is ambiguous due to the lack of parentheses in English (and natural languages in general):
(4) There will be a budget cut and taxes will increase or the crisis will continue.
Symbolizing “There will be a budget cut” with “p”, “Taxes will increase” with “q”, and “The crisis will continue” with “r”, (4) can be interpreted once as “(p∧q)∨r” (i.e. as an or-sentence that has an atomic and an and-sentence as constituents) and a second time as “p∧(q∨r)” (i.e. as an and-sentence that has an atomic and an or-sentence as constituents). It is impossible to figure out from (4) alone which of these interpretations is what the speaker means. That “(p∧q)∨r” and “p∧(q∨r)” have different meanings can be seen from the fact that, no matter what the truth value of q is, if p is false and r is true, the first sentence is true and the second is false. The ambiguity of (4) can be eliminated by using commas as parentheses. “There will be a budget cut and taxes will increase, or the crisis will continue” will then correspond to “(p∧q)∨r” and “There will be a budget cut, and taxes will increase or the crisis will continue” to “p∧(q∨r)”.
Let us see how we can represent symbolically sentences in which “or” is exclusive? Its meaning can be conveyed by the inclusive “or” and the expression “but not both” – “p or q, but not both”. The inclusive “or” corresponds to disjunction, “but” to conjunction, “no” to negation. So, “p or q, but not both” may be symbolized with “(p∨q)∧¬(p∧q)”. This formula tells us that at least one of “p” and “q” is true (“p∨q”) adding that it is not the case that both are true (“¬(p∧q)”).
If a sentence in the language of logic (a formula) contains conjunctions or disjunctions, they must be enclosed in parentheses, as for example in “(p∨q)∧¬(p∧q)”, “(p∧q)∨r”, or “p∧(q∨r)”. So, this is also the case in formulas of the type (α∧β)∧γ and (α∧β)∧γ. (We use Greek letters to represent arbitrary – atomic or compound – formulas.) The last two expressions involve nothing but conjunctions and differ only in the grouping with parentheses. No matter what the grouping with parentheses is, such containing only conjunctions formulas are true if all conjuncts are true and are false if one or more conjuncts are false. In the example, (α∧β)∧γ and α∧(β∧γ) are true if α, β and γ are all true, and are false if one or more of them are false. So, the expressions have the same meaning, which comes down to saying that all three sentences (α, β and γ) are true. Similarly, regardless of the grouping with parentheses, expressions formed by connecting formulas exclusively by disjunctions are true if at least one of the formulas is true and are false if all of them are false. For example, (α∨β)∨γ and α∨(β∨γ) are true if at least one of α, β and γ is true and are false if all three are false. The expressions have the same meaning, which comes down to saying that at least one of α, β and γ is true. Since grouping with parentheses is not important in such cases, we may not write parentheses at all. This will allow us to consider formulas of the type α ∧ β ∧ γ ∧ δ ∧ ... as corresponding to natural language sentences of the type “α, and β, and γ, and δ, and …” and formulas of the type α ∨ β ∨ γ ∨ δ ∨ ... as corresponding to “α, or β, or γ, or δ, or …”.
Examples of disjunction:
| p ∨ q | p | q |
| Either it was very noisy, or Bob was talking very quietly. | It was very noisy. | Bob was talking very quietly. |
| The brake has failed, or a tire has burst. | The brake has failed. | A tire has burst. |
| This summer we are going to the mountains or the sea. | This summer we are going to the mountains. | This summer we are going to the sea. |
| The witness will appear in court Wednesday unless the mafia kills him beforehand. | The witness will appear in court Wednesday. | The mafia will kill the witness before Wednesday. |
| (1) Symbolize the sentences. Indicate for each of the propositional letters you have used (p, q, r, …) which atomic sentence it symbolizes. |
| 1)3 | This car is not powerful, but it is very economical. |
| 2) | It’s not true that Bob is guilty and John isn’t. |
| 3) | Voldemort is not only mean but also cruel. |
| 4) | Mushrooms are neither animals nor plants. |
| 5) | The universe has no end in both time and space. |
| 6) | Tomorrow we will go by the lake unless it is raining. |
| 7) | I won’t be your friend anymore unless you apologize to me. |
| 8) | This did not happen today or yesterday. |
| 9) | Alice wants both ice cream and chocolate, but she won’t get either. |
| 10) | Bob will go to the mountains or the sea, with or without Alice. |
| 11) | Either the action was deliberate, and the defendant is guilty of murder, or the action was not deliberate, but the defendant has shown criminal negligence. |