Logic is the foundation for mathematical reasoning and is used heavily within the fields of computing , artificial intelligence and computer architecture. For example the arithmetic logic unit or ALU is designed using logic and performs arithmetic and bitwise operations on integer binary numbers within CPUs (Central Processing Unit).
A proposition begins with a declarative statement that declares that something is either true or false but not both. For example:
- Toronto is the capital of Canada (False)
- Washington D.C is the capital of the U.S.A (True)
- 1+1 =2
However some statements are not propositions because they do not declare anything such as :
- What time is it ?
- x + 1 = 2
- x + y = z
For propositions we use letters to denote propositional values which are p, q, r, s, . . . . In addition we use the letters T and F to denote True and False within truth tables.
Negation is denoted as ¬ (sometimes also written as ~) it turns a statement or a bit from true to false or false to true. For example , let P be a proposition. The negation of p , denoted by ¬ p will be it is not the case that p.
Example 2: Find the negation of the proposition “Micheal’s PC runs Linux”
Solution: The negation of the proposition is “Micheal’s PC does not run Linux”
Also a proposition that is already negated will become true as a double negation reverses the original change.
Conjunction
In the English grammar conjunctions are words like ‘but’,’and’,’or’ etc. that join two separate clauses. In terms of discrete mathematics the conjunction of p and q is denoted by p ∧ q and read as p “and” q. In order for a conjunction to be true both propositions must be true.
| P | Q | P ∧ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Disjunction
A disjunction is read p or q and is written as p ∨ q and is true whenever one of the two propositions is true. For example we have the proposition :
P: I am going to work
Q: I am going to school
As long as at least one of the two propositions is true, then the whole combined statement ( p ∨ q ) is true. However, if both propositions are false, then the whole combined statement is false.
| P | Q | P ∨ Q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Figure 3 – Truth table for OR
Inclusive “OR”
Inclusive OR is written as p ∨ q and refers to the disjunction above.
Exclusive “OR”
Exclusive OR is usually written as: P ⊕ Q. Only one of the conditions can be true, not both , for example: You get (only) soup or (only) salad with your meal ( cannot get both).
| P | Q | P ⊕ Q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Implication
Any if then statement is an implication The implication of propositions p and q is denoted as p→q and read as “if p then q” or “p implies q”. The hypothesis is p ( the if part) and the conclusion is q ( the then part). When the hypothesis is true then the conclusion must be true for the implication to be true. For example if you take out the trash then you get a dollar.
P: if you take out the trash
Q: you will get a dollar
Any time the hypothesis is false will be true because you can get a dollar for any reason regardless if you did not take out the trash plus it is not part of our condition and if you did not take out the trash and you did not get a dollar than it is true because you never did the if statement anyways.*
| P | Q | P→Q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Converse
Converse is the opposite of Inverse in terms of the order of P and Q. It is read as Q→P
P: if it rains today
Q: I will stay at home
Will be : If I will stay at home then it rains today
| P | Q | Q →P |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
PS: the converse and the implication have the same truth table
Inverse
Inverse is the negation of the conditional statement. If ~ not P then ~ Q.
P: If you live in Los Angeles
Q: You live in California
If you do not live in Los Angeles then you do not live in California.
This inverse is false because you can live in other cities such as San Diego or San Francisco and still live in California.
Contrapositive
Inverse is the negation of the converse statement. If ~ not Q then ~ P.
P: If you live in Los Angeles
Q: You live in California
If you do not live in California then you do not live in Los Angeles.
This contrapositive is true because you must live in the state of California to live in the city of Los Angles.
Biconditional
A biconditional statement occurs when the implication p→q and the converse Q→P are equivalent either true or false.
Implication : If i studied for my exam then I will pass.
Converse: If I passed than I studied for my exam
As you can see both are true , therefore it becomes a biconditional.
Example
I will pass if and only if I study hard.
p↔q
