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:
- Paris is in France
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.
Statements can be combined together into larger statements via connectives. Connectives include:
A conjunction is a compound statement in which two substatements are connected by ('and'). Below we have a 'truth-table'
A disjunction is a compound statement in which two substatements are connection by ('or').
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.
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 different variables, the truth table. Here is a truth table for the proposition .
Logical Equivalence, Tautology and Contradiction
Two propositions can be logically equivalent if the final columns of their truth tables are identical. For example: and .
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. is a tautology: it will always be true whilst is a contradiction:
Both tautologies and contradictions are often dismissed as useless assertions when simplifying expressions since they don't bring any new information.