Symbolic logic - First order predicate logic

Implication
premise --->consequence
p-->q

p q   -->
------------
0 0   1
0 1   1
1 0   0
1 1   1
used terms to express this are
1)p is sufficient for q     //
2)q is necessary for p
2)q if p
3)q whenever p
4)p only if q

Converse is q-->p
contrapositive  is -q --> -p
Biconditional  p <--> q     true when truth values same for p and q
statements like ' if and only if '  or  'p is necessary and sufficient for q'

Conjunction
A and B


Exclusive disjunction
(p Ú q) · ~(p · q) either p is true or q is true but not both

A compound proposition that is always true is Tautology and
which is always false is Contradiction
p and q are logically equivalent if p <---> q is tautology that is p and q have same truth values


Quantifiers

Universal Quantification

proposition function P(x) is true for all values of x in the universe of discourse
statement like for all x or for every x
equivalent to P(x1) and P(x2) and P.........(xn) where xi is universe of discourse

Everything  is
Everything is beautiful
∀y F(y)

Nothing is
 Nothing is beautiful
∀y ¬ F(y)

Existential Quantification

there exists an element x in the universe of discourse such that P(x) is true
statement like there is an x such that or there is at least one x such that
equivalent to P(x1) or P(x2) ...  p(xn)

Consider predicate F(y) which is true if y is beautiful
something is
 existential quantifiers tell that there is something or some y for which F(y) is true
something is beautiful
∃y F(y)

something is not
something is not beautiful
there is some y which is not beautiful
∃y ¬ F(y)

Nothing is
Nothing is beautiful
It is not the case that something is beautiful
 ¬∃y F(y)
that is negation of something becomes nothing

Everything is
everything is beautiful
It is not the case that something is not beautiful
¬∃y ¬ F(y)


Property of connectives
1)A -> B <===> -B -> -A
2)A->B <==> -A or B
3)∀y (P(y) and Q(y))  = ∀P(y) and ∀Q(y)
not true for OR that is universal quantification is not distributive over OR operator
4)∃y (P(y) OR Q(y))  = ∃y P(y) OR ∃y Q(y)
not true for AND that is existential quantification is not distributive over AND

Law of quantification
Distributive law
∀x (P(x) and Q(x)) <==>  ∀xP(x) and ∀xQ(x)
∃x (P(x) or Q(x))  <==> ∃y P(x) or ∃y Q(x)
∀xP(x) or ∀xQ(x)  ==> ∀x (P(x) or Q(x))
∃x (P(x) and Q(x))  ==> ∃y P(x) and ∃y Q(x)

example
∀x P(x) means (P(a) and P(b))
∃x P(x) means P(a) or P(b)
The best way  to understand the distributive property is to expand  the symbol ∀ and ∃ into basic definition of AND and OR
Consider  p(x) be cube(x) and q(x) be small(x) then
1)∀x cube(x) or ∀x small(x)  ==> ∀x (cube(x) or small(x))
 we can write the same as
Lhs: ( cube(a) and cube(b) ) or ( small(s) and small(t) )
these is true when either there exist two cubes a and b or two small objects s and t
Rhs: (cube(a) or small(a)) and (cube(b) or small(b))
if Lhs is true then this is also true because its true when either a  and b  is cube or small

but the reverse of the implication says that  if a is cube and b is small then lhs should be true but it is not so not bidirectional

Quantifier Independence
∀y∀x F(x,y)  <==>∀x∀y F(x,y)
∃y∃x F(x,y)  <==>∃x∃y F(x,y)
∃y∀x F(x,y)  ==>∀x∃y F(x,y)
but not ∀x∃y F(x,y)  ==>∃y∀x F(x,y)

Translating statement in predicate logic


1) Barber Paradox
the statement says "Barber shaves those residents who donot shave themselves"
∃y ∈ S : Barber(y) ∧ (∀x ∈ S : (Shaves(y, x) ↔ ¬Shaves(x, x)))
here paradox because when x=y  then it can never be true
remember to check for extreme cases always

2)
i) Some A's are B's
there exist some x that is both A and B

∃x(A(x) & B(x))

ii)Some A's are not B's
ther exist some x that is A and is not B
∃x(A(x) & ¬B(x))

iii)All A's are B's
for all x if it is A then it is B
∀x(Ax → Bx)

iv)No A's are B's
It is not the case that there exist some x that is A and is also B
¬∃x(Ax & Bx)
for all x if it is A then it is not B
∀x(Ax → ¬Bx)

3)implication we use with universal quantification and with existential quantification we use and connective
example S: Some lions don't drink coffee

L(x) :  x is lion
P(x) : x is pet
D(x) : x drinks coffee
S1:  ∃x (L(x) → P(x)) is wrong
S2 : ∃x (L(x) AND P(x)) is correct

4)statement involving : and, but, moreover, however,although, and even though are conjunction

5)unless means disjunction

http://www.earlham.edu/~peters/courses/log/transtip.htm 
www.niu.edu/~gpynn/205_11_handout.pdf