Friday, February 6, 2015

Propositional Logic / Sentential Logic

I. Introduction
Propositional logic (also called propositional calculus, sentential calculus, sentential logic, etc.) is a branch of logic that studies ways of joining simple (atomic) propositions to form more complicated propositions using logical connectives, and the logical relationships of these propositions.

To highlight the difference between term and propositional logic, think of the sentence "All dogs are mammals". Using term logic we would say the fundamental units of the sentence are the categories of dogs and mammals. In contrast, with propositional logic the fundamental unit of the sentence is the entire statement or proposition "All dogs are mammals". It's important not to equate propositions with sentences as a sentence can have more than one statement. For instance, the sentence “All dogs are mammals, and all cats are mammals too” clearly contains the two propositions.

II. Propositions
A proposition can be defined as a declarative sentence, or part of a sentence, that is capable of having a truth-value of either true or false, but not both. For the purpose of this post, the term "proposition" and "statement" are used interchangeably.

For example, "Paris is the capital of France." is a proposition with a truth value of "true" while the sentence, "Everyone born on Monday has purple hair" has a truth value of "false."

Some sentences are not propositions such as commands like "Close the door" or questions like "Is it hot outside?"

The smallest indivisible units in propositional logic are statements referred to as simple or atomic propositions. These are statements which are either true or false and cannot be broken down into other simpler statements. For example, "The dog ran" is an atomic proposition. Atomic propositions can be used to form complex propositions by using connective words (see connectives below). For example, "the dog ran and the cat hid" is a complicated proposition which combines two atomic propositions using the connective word "and".

III. The Language of Propositional Logic
Classical truth-function propositional logic utilizes a simple symbolic language to represent propositions expressed in natural language such as English. Simple (atomic) statements are represented by capital letters 'A', 'B', 'C', etc. The logical signs '∧', '∨', '→', '↔', and '~' are used in place of the truth-functional operators, "and", "or", "if... then...", "if and only if", and "not", respectively. Parentheses are used to group propositions similar to how they are used in algebra and arithmetic.

A. Connectives (logical operators)
Connectives (logical operators) are words or phrases used either to modify a statement or join simple statements together to form a complex statement. Though there are many connectives, the five basic ones are:


Here is a chart of which shows the logical operator (connectives formal name), the symbol and its natural language usage.

As there are no absolute standards in regards to symbols
 used in Propositional Logicdifferent authors use different symbols.
This link provides a list of alternate symbols you may come across.

1. Negation
Not-P.     For example, “It is not green.”

The negation of statement P, simply written "~P" in language PL, is regarded as true if P is false, and false if P is true. Unlike the other operators, negation is applied to a single statement. The corresponding chart can therefore be drawn more simply as follows:

Though the word "not" is generally thought of as the English equivalent of "~", it can be expressed in many ways such as:

It is not the case that...
It would be false to say that...
...failed to...

2. Conjunction 
p and q.     For example, “It is wet and it is cold.”

Conjunction is a truth-functional connective similar to "and" in English and written "∧" in PL. When dealing with a conjunction, you must consider both p and q. That is, a conjunction is true if and only if both conjuncts are true.

Though "and" is generally thought as the English equivalent to "∧" there are many ways it can be expressed. Some include:

both...and... well as...
...despite the fact that...

Though these may not seem similar to the word "and" it is important to remember that propositional logic treats as a conjunction any sentence whose truthfulness depends on both conjuncts being true and false if any or both conjuncts are false. For instance, the sentence "John loves Mary even though she barely tolerates him" is true only if both propositions "John loves Mary" and "She barely tolerates him" are true. If either or both are false, the whole proposition is false.

3. Disjunction
p or q (or both).     For example, “It is wet or it is cold.”

Disjunction is a truth-functional connective similar to "or" in English. The disjunction of two statements p and q, written in PL as "(p ∨ q)", is true if either p is true or q is true, or both p and q are true, and is false only if both p and q are false.

Though we say that "or" is the rough English equivalent to PL "∨", it should be noted that "∨" is used in the inclusive sense. More often than not when the word "or" is used to join together two English statements, we only regard the whole as true if one side or the other is true, but not both, as with the statement "Either we can buy the toy robot, or we can buy the toy truck; you must choose!" This is called the exclusive sense of "or". However, in PL, the sign "v" is used inclusively such as with the statement "Her grades are so good that she's either very bright or studies hard" which does not exclude the possibility of both.

Though the word "or" is generally used (imperfectly) as the English equivalent to "∨", there are other ways it can be expressed such as:


4. Conditional (material implication)
If p, then q.     For example, “If it is green, then it is heavy.”

The conditional is a connective similar to "if_then_" statements in English and generally represented as "→" in PL. The first simple statement in a conditional is referred to as antecedent and the second simple statement is known as the consequent. For example, with the statement "If you flip the light switch, the lights will go out" the antecedent is "You flip the light switch" and the consequent is "the lights will go out".

A conditional statement asserts that if the antecedent p is true, the consequent q will be true as well. In other words, a conditional statement is only false if the antecedent p is true and the consequent q is false.

5. Biconditional (material equivalence)
p if and only if q.    For example "A triangle is equilateral if and only if it is a triangle with three equal sides".

The biconditional is a connective similar to "if and only if" statements in English and generally represented as "↔" in PL. A biconditional is regarded as true if the antecedent and consequent are either both true or both false, and is regarded as false if either have different truth-values.

B. Scope, Parentheses and the Main Connective
Whenever more than one connective is used in a statement, there is a chance of ambiguity. Consider the statement S∨C∧T where S is "I will show you stamps", C is "I will make you some coffee" and T is "I will give you $1000". Hence, in English it would be written, "I will show you my stamps or make you coffee and give you $1000".

As it is presented, the statement is ambiguous and could be interpreted in two different ways:

1) "I will show you my stamps or make you coffee but in any event, I will give you $1000".

2) "Either I will show you my stamps or make you coffee and give you $1000".

The problem here is that we don't know what the scope is of either of the two connectives used in the statement. Does the disjunction in S∨C∧T connect S to C or does it connect S to C∧T? Does the conjunction in S∨C∧T connect C to T or does it connect S∨C to T?

To deal with this problem, parentheses are used to establish scope. So going back to our two interpretations of S∨C∧T, we would write:

1) "I will show you my stamps or make you coffee but in any event, I will give you $1000" as ((S∨C)∧T).

2) "Either I will show you my stamps or make you coffee and give you $1000" as (S∨(C∧T)).

*Note that in actual practice you will often find the outermost parentheses are omitted. 

In propositional logic, the main connective is the connective with the greatest scope in a statement. For example, with ((S∨C)∧T) we see that the scope of ∨ is limited to S and C while the scope of ∧ encompasses the entire statement. Therefore, in this example ∧ is the main operator.

Internet Encyclopedia of Philosophy: Propositional Logic
Introduction to Logic (second edition): Harry Gensler
Critical Thinking: An Appeal to Reason by Peg Tittle: Supplemental Chapter: Propositional Logic
Wikipedia: Negation
Wikipedia: Logical conjunction
Wikipedia: Logical disjunction
Logic Self-Taught: A Workbook