Truth Values & Logical Propositions

Statements

Logic is one of the most fundamental aspects of computer science - reasoning. Reasoning allows us to determine whether a particular statement is true or false. A statement is a collection of symbols that has a truth value - either false (F) or true (T).

Let us consider two statements:

  1. Paris is in France
  2. 2 + 2 = 6

Paris is in France is a true statement. We know that Paris is in France. The second statement is obviously false. Throughout this series, I will focus primary on the 'formal logic'. Formal logic doesn't concern itself with the meaning of the statements e.g. unicorns may or may not be real. It is all about logical progression of statements. This is the opposite to 'informal logic' where we can debate the existence of unicorns.

Combining Statements

Statements can be combined together into larger statements via connectives. Connectives include:

  • \wedge and
  • \vee or
  • \lnot not

A conjunction is a compound statement in which two substatements are connected by \wedge ('and'). Below we have a 'truth-table'

p q p\wedge q
F F F
F T F
T F F
T T T

A disjunction is a compound statement in which two substatements are connection by \vee ('or').

p q p \wedge q
F F F
F T T
T F T
T T T

Disjunctions are inclusive. In everyday uses 'or' are often exclusive: Tea or Coffee. You are expected to pick one, not both.

Finally we have negation.

p \lnot p
F T
T F

Propositions

A proposition is a statement in which the basic stubstatements are variables, each with F and T as possible values. It is worth noting that if a proposition has n different variables, the truth table. Here is a truth table for the proposition \lnot(p \wedge \lnot q).

p q \lnot q p \wedge \lnot q \lnot(p\wedge \lnot q)
F F T F T
F T F F T
F F T T F
F T F F T

Logical Equivalence, Tautology and Contradiction

Two propositions can be logically equivalent if the final columns of their truth tables are identical. For example: p \wedge (q \vee r) and (p \wedge q) \vee (p \wedge r).

We can also end up with tautology: a proposition that is true whatever the values of its variables. This is how Sheldon from The Big Bang Theory speaks:

The opposite of tautology is the contradiction; a proposition that is false whatever the values of its variables. Both tautology and contradiction can be easily seen by example below. p \wedge \lnot p is a tautology: it will always be true whilst p \wedge \lnot p is a contradiction:

p \lnot p p\vee \lnot p p \wedge \lnot p
F T T F
T F T F

Both tautologies and contradictions are often dismissed as useless assertions when simplifying expressions since they don't bring any new information.

Leave Comment

Your email address will not be published.

Please type the characters of this captcha image in the input box

Please type the characters of this captcha image in the input box