Logic Fundamentals

Verbal statements and other series of propositions can be evaluated symbolically to determine whether the statements "hold together" and under what circumstances the full statement (or series) can be considered to be true. This symbolic evaluation process is called Logic or Mathematical Logic. Logic also serves to identify extraneous propositions that can be disregarded.

Some Useful Symbols

• ⇒ implies
• ⇔ if and only if, is necessary and sufficient for, is equivalent to
• ∧ conjunction between propositions, means “and”
• ∨ disjunction between propositions, means “or”
• ∀ universal quantifier, means "for every", "for each", "for all"
• ∃ existential quantifier, means “there exists”
• ∴ therefore
• ∈ is an element of
• ∉ is not an element of

Logic Definitions

• proposition - a statement that is either true or false
• counterexample - an example that proves a universal proposition to be false
• negation -- takes the truth value opposite to that of the proposition being negated
• hypothesis - the "if" part in a complex statement (If this then that.)
• conclusion - the final answer in a complex statement
• truth table - gives all possible true/false values for given propositions
• tautology - a statement which is always true regardless of the truth value of its basic propositions ("I will either come to your party or I won't" is always true.)

Symbol          Proposition

p                    the object is a ball

q                    the object is black

p ∧ q              the object is a black ball

p ∨ q              the object is either black or it is a ball

~p                   the object is not a ball

~(p ∧ q)          the object is not a black ball

~(p ∨ q)          the object is neither black nor a ball

p ⇒ q              if the object is a ball, then it is black

p ⇔ q              the object is a ball if and only if it is black

Examples of writing a statement with symbols

1) If the object is not black, then it is not a ball.

Write:

     object is not black as ~q

     object is not a ball as ~p

     ⇒ is the if-then symbol, so the whole sentence is ~q ⇒ ~p

2) If the object is a black ball, then it is not a chair (add proposition s = object is a chair)

Write:

     object is a black ball as (p ∧ q) because it’s black and it’s a ball

     object is not a chair as ~s

     therefore (∴) the whole sentence is (p ∧ q) ⇒ ~s

Given the propositions p and q, and the composite proposition p ⇒ q, and the following symbol definitions

            p -- the object is a ball

            q -- the object is black

            p ⇒ q -- if it is a ball, then it is black

we can see by looking at the truth table that:

If both p (the object is a ball) and q (the object is black) are true, then p ⇒ q has not been contradicted and is true.

If p is true but q isn’t (it is a red ball), then p ⇒ q is not true because p ⇒ q says that balls are black -- which is contradicted by the fact that the ball is red.

If p is false (the object is a chair) and q is true (it is black) then p ⇒ q has not been contradicted and is thus true (because p ⇒ q isn’t about chairs)

If p is false and q is false (it’s a red chair), then p ⇒ q is still true (again because p ⇒ q hasn't been contradicted)

Show that p ⇒ q is the same as ~q ⇒ ~p

This truth table shows that no matter whether proposition p is true or false, or whether proposition q is true or false, the statement "if p then q is the same as if not q then not p" is true.

Using our ball example, this means that the statement: “if the object is a ball, then it is black” is the same as “if the object is not black, then it is not a ball”.