Thursday 28 February 2013

Predicates And Quantifiers

Introduction Of Predicates 

 A pred­i­cate is a state­ment for which we can input val­ues, such that it is turned into a state­ment and there­fore true or false. We use func­tion nota­tion (with­out type for input/output, though you can spec­ify the domain in the state­ment) for this: P(x)  is such.


n general you have predicates in the form of:
P(x) – this is a unary predicate (has one variable)
P(x,y) – this is a binary predicate (has two variables)
P(x1, x2, x…….., xn) – this is an n-ary or n-place predicate – (has n individual variables in a predicate)

For example x + y= z is written as:
Sum(x,y,z)
This stands for the predicate x + y = z

Quantifiers 

A predicates becomes a propositional when we assign it fixed value
 However , another way to make a predicate into a proposition is to quantify it.That is , the predicate is true or false for all possible values in the universe of discourse or for some value(s) in the universe of discourse.

      Quantification can be done with 2 quantifiers : 

1.       Universal quantifiers  ( ∀ )
§  P(x) is the proposition “P(x) is true for all values of x in the universe of disourse.
§   Read as “for all x”
§  ∀xP(x)
 2.        Existential quantifiers (∃)
§  P(x) nis the proposition “ There exist and x in the universe of discourse such that P(x) is true.
§  Read as “there exists an x”
§  ∃xP(x)


Examples of quantifiers

 “All lions are fierce.” 

 “Some lions do not drink coffee.” 


 “Some fierce creatures do not drink coffee.”

“All hummingbirds are richly colored.”

 “No large birds live on honey.”

 “Birds that do not live on honey are dull in color.”

 “Hummingbirds are small.”

Every glass in my recent order was chipped.

Some of the people standing across the river have white armbands.

Most of the people I talked to didn't have a clue who the candidates were.
A lot of people are smart.

That wine glass was chipped

Someone gets mugged in New York every 10 minutes










Prepositional Equivalence

Prepositional Equivalence 

Definition: two propositional form on the same variables (logically) equivalent if they have the same result column in their truth table notation

žTautology = proposition that is always true
žContradiction = proposition that is always false
žContingency = proposition that is neither tautology nor contradiction

Example of tautology p V¬p


Example of contradiction: p ∧ ¬p


Contingency 

Two compound proposition p and q are logically equivalent if the columns in a truth table giving their truth values agree.


p ≡q if and only if p  q is a tautology.










Prepositional Logic

Prepositional Logic 

Definition : A proposition or statement is a sentence which is either true or false If a proposition is true, then we say its truth value is true, and if a proposition is false, we say its truth value is false.

Example : 

1. The sun is shining. (True)
2. The sum of two prime numbers is even. (False)
3. 3+4=7 (True)
4. It rained in Austin, TX, on October 30, 1999. (False)
5. x+y > 10 (True)
6. n is a prime number. (True)
7. The moon is made of green cheese. (False)

Prepositional Variables 

Definition : A propositional variable represents an arbitrary proposition. We represent propositional variables with uppercase letters.

Example : We use letters P, Q, R, S, to denote propositional variables.
we may use the letter P to refer to “All penguins are birds” and the letter S for “Socrates is mortal”. We can then perform logical operations on these words, and say something like P ∧ S, or “All penguins are birds, and  Socrates is mortal.”

Types of truth tables 

1.     Negation

~
P
F
T
T
F

2.    Conjunction

P
.
q
T
T
T
T
F
F
F
F
T
F
F
F

3.    Disjunction

P
V
q
T
T
T
T
T
F
F
T
T
F
F
F


4.    Material Equivalence

P
Ξ

q
T
T
T
T
F
F
F
F
T
F
T
F

5.    Material Implication

P
É

q
T
T
T
T
F
F
F
T
T
F
T
F