Logic

Definition:The study of principles of valids using rules of operate on a statement or several statements to reach a correct solution.

Truth Value;
Definition:Any sentence or statements which can be either true or false but not both. That sentence can be assigned the truth value, true ( T or 1) or False (F or 0).

Proposition
A declarative sentence that is either true or
false, but not both.
Examples:
• CS19 is a required course for the CS major.
• Tolkien wrote The Lord of the Rings.
• Pigs can fly.
Non-examples:
• What a beautiful evening!
• Do your homework.
Compound Proposition
One that can be broken down into more
primitive propositions.
E.g.,
• If it is sunny outside then I walk to work; otherwise
I drive, and if it is raining then I carry my umbrella.
This consists of several primitive propositions:
t = “I carry my umbrella”
r = “I drive” s = “It is raining”
p = “It is sunny outside” q = “I walk to work”
Connectives: “if… then”, “otherwise”, “and”

Compound Proposition
If it is sunny outside then I walk to work; otherwise I
drive, and if it is raining then I carry my umbrella.

p = “It is sunny outside” q = “I walk to work”
r = “I drive” s = “It is raining”
t = “I carry my umbrella”

If p then q; otherwise r and if s then t.
If p then q and (if not p then (r and (if s then t))).
p implies q and ((not p) implies (r and (s implies t))).


Logical Connectives
Used to form compound propositions from
primitive ones.

There are different types of compound statements which can be formed by using NOT, OR , AND etc. Let us discuss one by one in detail.


Negation
If p is any statement, then the statement “not p” is called the negation of p denoted by "~p".
~p is true, when p is false and ~p is false, when p is true.









Conjunctions
If p and q are two statements, then the compound statement “p and q”, is called the conjunction
denoted by “p q”. p q is true when both p and q are true.
The truth table for p q:











Disjunctions
If p and q are two statements, then the compound statement “p or q” is called the disjunction, denoted
by "p v q", p v q is false when both p and q are false.
The truth table for p v q is given below:










Conditional statement
If p and q are two statements, then the compound statement "If p then q" is called the conditional
statement denoted "p q". p q is false when p is true and q is false.









Note:
(i) In p q, p is called the antecedent and q is called the consequent.
(ii) q p is called the converse of p q
(iii) ~p ~q is called the inverse of p q
(iv) ~q ~p is called the contrapositive of p q




Biconditional statement
If p and q are two statements then the compound statement “p if and only if q”, is called the biconditional
statement denoted by “p q”. “p q” is true when both p and q are
true or when both p and q are false.










Note:
Suppose a compound proposition is given, we first split it into simple propositions containing a single
connective. Using the rules discussed above, we construct the truth table in the form of columns and
the last column gives the truth value of the given proposition for different combinations of the truth
values of its components.
Tautology
A compound statement is said to be a tautology, if it is always true for all possible combinations of the truth values of its components.
A tautology is also called a theorem or a logically valid statement pattern.
Contradiction
A compound statement is said to be a contradiction, if it is always false for all possible combinations of the truth values of its components.
Note:
(i) The negation of a tautology is a contradiction.
(ii) The negation of a contradiction is a tautology.
Logical Equivalence
Two compound propositions p and q are said to be logically equivalent, if their truth values are the same for each different combination of the truth values of the components involved in them. If p and q are logically equivalent, then it is represented by p q.

For example,
show that (p q) r = p (q r)
Suggested answer:

Observe that last two columns are identical.
(p q) r p (q r)