Logic and Quantifiers
This page discusses Logic and Quantifiers found in many Real Analysis and logic classes. Definitions with discussion follow.
- proposition
- an assertion that is either true or false but not both. A proposition is called simple or atomic if it is made up of only one proposition. A proposition is compound if it consists of one or more simple propositions with one or more logical connectives.
- logical connective
- joins simple propositions together to create a new proposition which may differ in truth value
- truth value
- the validity of a proposition. The truth value of a statement may be true or false or in some cases neither.
- truth table
- a truth table for a proposition displays every possible truth value for each simple proposition involved and the truth value of the corresponding compound proposition
- logically equivalent
- two compound propositions are logically equivalent if they have the same truth table
- tautology
- a proposition that is always true
- contradiction
- a proposition that is always false
- quantifier
- a quantifier imposes a condition on a proposition
An example of a proposition could be "My cow is an albino." The truth value of the proposition is either true or false but not both(either my cow is white or it isn't.) Propositions do not always have to be true, for example, "My cow is purple" is still a proposition even though the truth value is false.
Logical Connectives
Let P = "My cow is an albino" and let Q = "My cow likes chocolate" The following table lists common logical connectives, their symbols,the truth table for each connective, and an example using proposition P and Q.
You can think of a truth table as listing each possibile truth value for the simple propositions, and the outcome when the truth values are used correctly with a logical connective. For example, consider the the first line of the truth table for negation. The first column says that P is a true statement i.e., it is true that my cow is an albino. The second second column tells me since P is a true statement, the negation of P is false. Since P originally was true if we include the word "not" then the sentence is false. Hence the F in the second column.
| Connective | English | Symbol | Truth Table | Example | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| negation | not | ~ |
| My cow is not an albino. | |||||||||||||||
| disjunction | or | v |
| My cow is an albino or my cow likes chocolate | |||||||||||||||
| conjunction | and | ^ |
| My cow is an albino, and my cow likes chocolate | |||||||||||||||
| conditional | If ,then | $\rightarrow$ |
| If my cow is an albino, then my cow likes chocolate. | |||||||||||||||
| biconditional | if and only if | $\iff$ |
| My cow is an albino if and only if my cow likes chocolate. |
Use of the disjunction asserts one of the two statements joined by the v is true. Hence if either or both of the sentences are true, then the whole sentence is true. Note the disjunction is only false if neither of the statements are true which makes sense. If you assert one of two false statements is true then you are talking nonsense.
The conjunction ^ also means the same thing as the "and" used in the English language. If two sentences are joined by an "and" then you know the speaker is saying both of the sentences are true. Note the conjunction is only true if both P and Q are true.
The conditional is a little bit tricky to rationalize. P and Q in the conditional have special names. P is called the antecedent. P is the part of an if-then statement that supposes something. Q is called the consequent. Q is the result of supposing that P is true. Note the only instance when a conditional is false is when P is true and Q is false which makes sense because if something logically following from a true sentence is false then there is a problem with the if-then statement. For example, consider the statement "If it is raining there are clouds in the sky." If it was raining and there were no clouds in the sky you would be making a false statement.
There is no real English equivalent to the biconditional. However, the biconditional is useful for theorems in mathematics. Note the only instances when a biconditional is false is when there is disagreement in the validity of P and Q. An example proposition for biconditional could be "I am alive if and only iff I am breathing." This proposition is true when P and Q are both true or when not-P and not-Q are true i.e., "I am not alive if and only if I am not breathing." If P is true, Q can not be false. An abbreviation for if and only if is iff.
Tautologies and Contradictions
An example of a tautology is "I am wearing white or I am not wearing white." That sentence is always true regardless of what you are wearing. An example of a contradiction would be "I have exactly five dollars in my bank and I do not have exactly five dollars in my bank." P and Q are joined by "and" which is only true if both P and Q are true. However P and Q can not both be true at the same time, thus making a contradiction.
