II. Sentential Logic

Propositions

Negation

Disjunction

Conjunction

Conditional

Biconditional

Tautologies

Propositions

A proposition is a statement, which in English would be a declarative sentence. Every proposition is either true or false. This condition is sometimes referred to as a "dichotomy" or an example of "binary logic". This restriction to only two "truth values" is a source of difficulty in "real life" where ambiguity and "shades of truth" often cloud our reasoning and decisions. Another problem with this "truth functional" definition of a proposition is the contextual dependence on space and time. Consider the simple declarative sentence, "It is raining". The truth value of such a sentence depends on where and when you are! Nevertheless, for any observer the statement is either true or false once a "satisfactory" definition of "raining" is agreed upon.

A proposition is said to be simple or atomic if it has no connectives or quantifiers and in these notes will be represented by a single letter of the alphabet such as p or q . The truth-functional structure of such a statement can be represented by a truth table in which all possible truth values are displayed. A simple truth table is shown below.

Note: All possible truth values of all three propositions are displayed. Since each of the three propositions has 2 possible truth values, there are 2³ = 8 rows in the truth table. More generally, if there are n propositions there will be 2ⁿ rows in the corresponding truth table.

Below are the five standard connectives used to form compound propositions from atomic propositions.

1. Negation (NOT)

2. Disjunction (OR)

3. Conjunction (AND)

4. Conditional (IF…THEN…)

5. Biconditional (IF AND ONLY IF)

1. Negation (NOT) transforms a proposition into its opposite truth value, i.e., ~ p is true whenever p is false and ~ p is false whenever p is true. For example if p is the proposition, "George Washington was born in 1732", then ~ p is the proposition "George Washington was not born in 1732". The truth table for negation is shown below.

A statement like ~ (~ p) is equivalent or can always be replaced by the simpler statement p. For example, the statement "John is not dishonest" is the negation of "John is not honest" and is equivalent to "John is honest".

2. Disjunction (OR) is sometimes referred to as inclusive OR and is true as long as one of the "disjuncts" that comprise it is true. For example, the statement in a college course catalogue, "Students must take a statistics course or a logic course to graduate", would seem to imply that a student has met the requirement if she/he has taken a statistics course, or has taken a logic course, or has taken both a statistics and a logic course. In many everyday situations, OR means the exclusive OR which precludes both disjuncts being true. For example, the statement "Sally can have cake or ice cream for dessert", might often be interpreted as saying that she can have cake or ice cream but not both at the same time. The truth table for OR is shown below. Note: is false if and only if both p and q are false. OR is a commutative operator, i.e., is always the same as.

p	q
True	True	True
True	False	True
False	True	True
False	False	False

This truth table can be entered into an Excel Spreadsheet by using the Excel Logical (or Boolean) Function OR as shown below.

 The output of the Excel OR function generates the results shown below.

3. Conjunction (AND) is used to join two statements ("conjuncts") with the understanding that the conjunction is true if and only if all conjuncts are true. The truth table for AND is shown below. Note: is true if and only if both p and q are true. Like the OR operator, AND is commutative, i.e., is always the same as .

p	q
True	True	True
True	False	False
False	True	False
False	False	False

This truth table can be entered into an Excel Spreadsheet by using the Excel Logical Function AND as shown below.

 The output of the Excel AND function generates the results shown below.

When more than one connective is used in a compound proposition, the order in which we apply them to the simple propositions in the sentence can cause confusion. For example, isto be interpreted as the disjunction of p with the conjunction of q with r, or as the conjunction with r of the disjunction of p with q? To be unambiguous, standard order of operation rules (analogous to those used in arithmetic) were developed so that anyone reading the proposition understands what it says. According to this convention, the above proposition means the disjunction of p with the conjunction of q with r. This is because (AND) has higher priority than(OR), and therefore propositions connected by are done first. The standard priority list is. This means that if no grouping symbols are present, connectives will be applied in this order proceeding from left to right. In the compound proposition, we first negate p then take the conjunction of this with q. Grouping symbols, , are used to either override the normal order or to make the intended order more explicit. To negate the conjunction of p with q, we would write. Except for expressions like in which simple propositions are negated, these notes will make free use of grouping symbols to make compound statements easier to read and understand.

4. Conditional (IF…THEN…) is probably the most common form of a conjunction in logic and mathematics. The basic idea is that the truth of the condition expressed in proposition p is sufficient to guarantee the truth of proposition q. One of the oldest rules of inference which forms the core of Aristotelian logic is the syllogism consisting of two premises and a conclusion.

Here the symbol is shorthand for therefore. This particular form of a syllogism is sometimes called the Law of Detachment or in Latin modus ponendo ponens. The core idea of (often "read" as p implies q) is that if p is true, q must be true. Stated differently, it would be impossible for p to be true and q to be false, i.e., if q is false then p must be false. A true p never leads to a false q. On the other hand, if p is false it is quite possible for q to be either true or false (the guarantee is now void). This means that is always true if p is false (i.e., ~ p is true). From these consideration we see that is equivalent to (i.e., always has the same truth value as) . Thus, the statement is always true if ~ p is true or if p is true and q is true. The only way can be false is when p is true and q is false. Since is equivalent to , which is equivalent to , we have that is equivalent to .

 The statement is called the contrapositive of and from a logical point of view always says the same thing as . These facts are summarized below in the following truth table.

p	q		~ p		~ q
True	True	True	False	True	False	True	True
True	False	False	False	False	True	False	True
False	True	True	True	True	False	True	False
False	False	True	True	True	True	True	True

Note: the truth values for are not identical to the truth values of . When p is true, q can not be false if is true; however, when is true, q can be false when p is true. The statement is called the converse of and does not say the same thing. Thus unlike OR and AND the conditional operator is not commutative, i.e., is not necessarily the same as its converse. The converse, , is however equivalent to its own contrapositive, , which is called the inverse of .

The conditional can be expressed in the following ways in English.

p is a sufficient condition for q. (If p is true then q is true regardless of anything else.)

q is a necessary condition for p. (If q is not present, i.e., q is false, then p is not present.)

Unless q not p.

Not p unless q.

Not p without q.

To illustrate these connections suppose there were a college that required the passing of a statistics course for graduation. Let s be the proposition "John passes a statistics course." and g be the proposition "John graduates." The intent of the rule is clearly embodied in the conditional . If we know John graduated, then he must have passed statistics. Note the converse need not be true. John could pass the statistics course, but then later drop out of school for other reasons. The condition g is sufficient for s. Graduating guarantees a statistics course was passed! The condition s is necessary for g. John will not graduate without passing statistics (~ g without s). Unless John passes statistics he will not graduate (unless s not g).

The term necessary condition may seem confusing when time ordering and "pre-conditions" are considered. For example, let w be the proposition "the Packers beat the Vikings" and p the proposition "the Packers make the playoffs". In the conditional , p is a necessary condition for w, i.e., for the Packers to beat the Vikings it is necessary that the Packers make the playoffs. This certainly seems a strange statement if a necessary condition is to be interpreted as a pre-condition in time! It does make sense logically in the sense that if p is "lacking", i.e., the Packers fail to make the playoffs, then it must be true that w didn't happen, i.e., the Packers didn't beat the Vikings. Note: the converse need not be true. Other conditions (the results of other games) could get the Packers into the playoffs even if they lose to the Vikings!

The conditional connective has bothered many people. By the rules of , the following are all true!

If George Washington lived on Mars, then Abraham Lincoln was never president. (FalseFalse is True)

If pigs can fly, then Nazi Germany lost World War II. (FalseTrue is True)

If birds can fly, then Madison is the capitol of Wisconsin. (TrueTrue is True)

Many people would regard these statements as either nonsense or, at best, examples of a "non-sequitur". There seems to be no "logical" connection between the "p's" and the "q's". The flying of birds seems irrelevant to the location of Wisconsin's capitol city. Despite such objections, we will continue to use the conditional connective as it was defined!

5. Biconditional (IF AND ONLY IF) is a statement of equivalence. This means that if is true, then the truth values of p and q are identical. In some sense p and q are identical, they are just restatements of the same proposition. Alternatively, means q can be taken as the definition of p or p can be taken as the definition of q. Any occurrence of p in an argument can be replaced with q with no loss or change in meaning.

means p and q are either both true or both false. means that p is both necessary and sufficient for q and q is both necessary and sufficient for p. Thus,is equivalent to .

The truth table for is shown below.

p	q
True	True	True	True	True	True
True	False	False	False	True	False
False	True	False	True	False	False
False	False	True	True	True	True

Actually, we only really need two connectives, for example conjunction, conditional and biconditional can all be defined in terms of negation and disjunction.

As this illustrates, while we don't need the additional connectives, their absence would greatly complicate compound statements we might want to consider.

An additional connective, which is sometimes used, is the Exclusive OR which is false if both disjuncts p and q are true. It can be defined as follows :

The truth table for Exclusive OR is shown below.

p	q
True	True	False
True	False	True
False	True	True
False	False	False

Tautologies

A compound proposition whose truth-values are all true is said to a tautology. The negation of a tautology has all false truth values and is called a contradiction. A tautology is true regardless of the truth values of its constituent atomic propositions just as a contradiction is false regardless of the truth values of its propositions.

The compound proposition is a tautology. It's also pretty meaningless. Nevertheless, in any argument we can introduce this statement and sometimes it actually gets us somewhere!

The compound proposition is a contradiction. It some sense it is the parent of all lies since it immediately and without shame purports to tell us something and then denies that same thing!

 If the compound propositions p and q always have has the same truth values, then the biconditionalwill always be a tautology. In sentential logic all theorems are tautologies and all tautologies are either axioms or theorems. Thus, one can determine if a given proposition is an axiom or theorem by constructing its truth table. If the proposition is a tautology, it must be an axiom or theorem of sentential logic. This is illustrated in the following Excel spreadsheet, which establishes DeMorgan's Rules for negating conjunctions and disjunctions.

The output of this spreadsheet is shown below.

Since and have identical truth values must be a tautology. Similarly, since and have identical truth values, is a tautology.

Note: The use of DeMorgan's Rules demonstrates that the negation of the tautology is the contradiction and the negation of the contradiction is the tautology .