Logic is commonly known as the science of reasoning, and is used to establish the validity of arrangements.
It is not so much concerned with what the argument is about, but more with providing rules so that the general form the argument can be judged as sound or unsound.
The rules which logic provides allow us to assess whether the conclusion drawn from stated premises is consistent with those premise or whether there is some faulty step in the deductive process which claims to support the validity of the conclusion.
Here rare some of the reasons to study Mathematical Logic,
- At the hardware level the design of logic circuits to implement instructions is greatly simplified by the use of symbolic logic.
- At the software level knowledge of symbolic logic is helpful in the design of programs.
Many algorithms and proofs use logical expressions such as,
If p then qor
If p1 AND p2 , then q1 OR q2Therefore it is necessary to know the cases in which these expressions are TRUE or FALSE, that is, to know the ‘truth value’ of such expressions.
We also investigate the truth values of quantified statements which are statements that use the logical quantifiers for every and there exist .
Since this is a beginner’s guide, we are covering the fundamentals of Mathematical Logic. In case you want to keep learning, we have added a list of books to refer at the end of the guide.
Content
Propositions and Compound Statements
A proposition (statement or verbal assertion) is a declarative (meaningful / can be determined ) statement which is either TRUE or FALSE, but not both simultaneously.
We sometimes refer to propositions as statements in the English Language, such assertions are made by means of declarative sentences.
Consider, the following 9 examples,
| Ice floats on water. | TRUE |
| 2 + 2 = 4 | TRUE |
| A Triangle has 3 vertices. | TRUE |
| 2 + 3 = 7 | FALSE |
| 6 > 24 | FALSE |
| China is in Europe. | FALSE |
| The difference of two primes. | |
| What time is it? | |
| Long live the queen! |
The last 3 are not propositions ( statements ) in our sense since we cannot assign a truth value to them. Thus demands, questions and exclamations are not propositions.
Let us consider two more examples.
- This rose is white.
- Tomorrow is my birthday.
The truth values of the above two prepositions depend on the circumstances / context in which the preposition was stated/uttered. So it may sometimes be TRUE and sometimes be FALSE. either way, the statement must contain enough information for us to be able to decide a truth value.
Important
Conventionally lowercase letters such as p,q,r will be used to represent propositions (symbolize statements). They also stand for arbitrary propositions.
e.g.
- p : Manchester of Scotland is in Scotland.
- q : Mammoths are extinct.
Compound Propositions
All the propositions that are considered up to now are compound simple propositions, since they make only single statement. which cannot be broken into simpler propositions.
A combination of two or more simple propositions is a compound proposition.
Many propositions are composite; that is composed of sub propositions and various connectives.
e.g.
- Roses are red and violets are blue.
- John is smart or he studies every day.
The fundamental property of a compound proposition is that its truth value is completely determined by the truth values of its sub prepositions together with the way in which they are connected to form the compound propositions.
Logical Connectives and Truth Tables
The devices which are used to link pairs of proposition are called logical connectives.
The truth value of any compound statement is completely determined by,
- The truth values of its component simple propositions.
- The particular connective. or connectives, used to link them.
The most basic logical operations are,
| Operation | Keyword |
| Conjunction | AND |
| Disjunction | OR |
| Negation | NOT |
The propositions that form a propositional function are called the propositional variables.
For the following topics, let p, q, r be propositions. (by convention)
Conjunction ( p ∧ q )
Any two simple propositions can be combined by the word and between them to form a compound proposition called the conjunction of its two original component simple propositions.
Symbolically ;
p ∧ q , p AND q denote the conjunction of p and q.
Definition :
If p is TRUE and q is TRUE, then p ∧ q ( read ‘p and q’ ) is TRUE; otherwise p ∧ q is FALSE.
e.g.
Let p : The sun is shining. , q : Pigs eat turnips. Then p ∧ q : The sun is shining and pigs eat turnips.
Since p ∧ q is a proposition, it has a truth value which only depends on the truth values of p and q.
Definition :
A table which summarizes truth values of propositions for each possible outcome of its variables is called a truth table.
| p | q | p ∧ q |
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
Since the truth values of p ∧ q for each possible pair of truth values of p and q are seen; the conjunction p ∧ q is TRUE only when both p and q are TRUE. Otherwise the conjunction is fake.
Disjunction ( p ∨ q , p ⊕ q )
Any two simple propositions can be combined by the word or to form a compound proposition called the disjunction, of its two original component simple propositions.
Symbolically,
p ∨ q, p OR q denote the disjunction of p and q.
Definition :
If either p is TRUE or q is TRUE, then p ∨ q ( read ‘p or q’ ) is TRUE; otherwise p ∨ q is FALSE.
e.g.
Let p : Ice floats on water. , q : 2+2=5 ; Then p ∨ q : Ice floats in water or 2+2=5.
Since p ∨ q is a proposition; it has a truth value which depends only on the truth values of p and q.
| p | q | p ∨ q |
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
Since the truth values of p ∨ q for each possible pair of truth values of p and q are seen; the disjunction p ∨ q is false only when both p and q are false. Otherwise, the disjunction is false.
In logic; we distinguish two types of disjunctions.
- The inclusive form.
- The exclusive form.
The or in natural language is ambiguous in conveying which type of disjunction is implied. When two simple proposition are combined using or, context will often provide a clue as to whether the inclusive or exclusive sence is intended.
Sometimes it is used in the sence,
- “p or q or both” – at least one of the alternatives occurs.
- e.g. “Applicants for this post must be over 25 or have at least 3 years relevant experience.”
- “p or q but not both” – exactly one of the two alternatives occurs.
- e.g. “At 4.00 p.m. , I will go for swimming or to play golf”
Therefore ‘1.’ should be interpreted inclusively while ‘2.’ is interpreted exclusively.
Symbolically,
- Inclusive disjunction – p ∨ q
- Exclusive disjunction – p ⊕ q or p ⊻ q
p ⊕ q , p ⊻ q , p XOR q denote the conjunction of p and q.
Definition :
When exactly one of p and q (one or other, but not both) is TRUE , then p ⊕ q ( read ‘p exclusive or q’ ) is TRUE; otherwise p ⊕ q is FALSE.
| p | q | p ⊕ p | p ⊕ q |
|---|---|---|---|
| F | F | F | F |
| F | T | F | T |
| T | F | F | T |
| T | T | F | F |
Special Note
p ⊕ p = T
| p | q | r | p ⊕ q | (p ⊕ q) ⊕ r |
|---|---|---|---|---|
| F | F | F | F | F |
| F | F | T | F | T |
| F | T | F | T | T |
| F | T | T | T | F |
| T | F | F | T | T |
| T | F | T | T | F |
| T | T | F | F | F |
| T | T | T | F | T |
Negation ( ~p )
The operation which has the effect of reversing the truth value of the proposition is called negation.
e.g.
- p : 6 is a prime number
- ~p : 6 is not a prime number
Symbolically,
~p, ¬p, NOT p denotes the negation of p.
Definition :
If p is TRUE, then ~p ( read ‘not p’ ) is FALSE; if p is FALSE, then ~p is TRUE
If p symbolizes a proposition, ~p symbolizes the negation of p. ~p has a truth value which depends only on the truth value of p.
| p | ~p |
|---|---|
| F | T |
| T | F |
Important
There are several alternative ways of stating the negation of a proposition.
e.g.
p : All engineers are good at mathematics.
~p:
- It is not the case that all engineers are good at mathematics.
- Not all engineers are good at mathematics.
- Some engineers are not good at mathematics.
- At least one engineer is not good at mathematics.
To be the negation; the second statement must be FALSE in all circumstances that the first is TRUE.
Hence,
~p ≠ No engineer is good at mathematics.
This is not the negation of the proposition p.
Any statement can be negated by prefixing the given statement with “It is not true that …” , but great care must be taken with any other form of wording.
e.g.
- p : All Englishmen have brown hair.
- ~p : At least one Englishmen does not have brown hair.
Tautologies and Contradictions
There are certain compound propositions which have the surprising property that they are always TRUE no matter what the truth values of their simple components. Simply, if we prepared a truth tables like previously for a tautology, the last column will only contain T values.
And also there are other compound propositions which are always false no matter what the truth values of their simple components.
In both cases, this property is a result of the structure of compound propositions.
Definition :
A tautology is a compound proposition which is TRUE, regardelss of the truth values of the basic simple propositions of which it is compromise of.
A contradiction is a compound statement which is FALSE, regardless of the truth values of the simple propositions of which it is compromised of.
Symbolically,
- Tautology :- T or t
- Contradiction :- F or f
| p | ~p | q | p ∨ ~p | p ∧ q | ~ (p ∧ q) | (p ∧ q) ∨ ~(p ∧ q) |
|---|---|---|---|---|---|---|
| F | T | F | T | F | T | T |
| T | F | F | T | F | T | T |
| F | T | T | T | F | T | T |
| T | F | T | T | T | F | T |
∴ p ∨ ~p is a tautology.
∴ (p ∧ q) ∨ ~(p ∧ q) is a tautology.
Also it can be shown,
p ∧ ~p is a contradiction.
(p ∧ q) ∧ ~(p ∧ q) is a contradiction.
Hackrly 
Leave a comment