Logic

1.PROPOSITIONAL LOGIC

Material Equivalence - Asserts the statements always have the same truth value                              

2.PROPORTIONALEQUIVALENCES

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

Contigency

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.

3.PREDICATES AND QUANTIFIERS

 Proposition 

 a possible condition of the world about which  want to say           

       something.

                 

Propositional Variables

a variable which can be the true or false.

 Types of Truth Table 

Negation

       Conjunction - assert both statement are true

Disjunction - Asserts at least one statement is true

Material implication -  assume it is true unless proven false

Introduction to Predicates

➳ Also known as propositional function

➳ Sentences that contain variable either true or false depending on value assign to variables.

➳Denote by P(x)

Exp : P(x): x>3

Definition Quantifiers

➳Quantifers are words that refer to quantities such as "some" or "all" and tell for

      how many elements a given predicate is true

 Two type  of quantifiers

 universal quantifier:

DEFINITION

v  predicate is true for all values 

v  symbol:   "

v read: for all

example

P(x) : “x must take a discrete mathematics course”

Q(x):  “x is a computer science student”.

Express the statement “Every computer science student

must take a discrete mathematics course”.

"x(Q(x) → P(x))

Express the statement “Everybody must take a discrete

mathematics course or be a computer science student”.

"x(Q(x) ˅ P(x))

existential quantifier:

 DEFINITION

v  predicate is true for some values 

v  symbol: $ 

v  read: there exists

P(x) : “x must take a discrete mathematics course”

Q(x):  “x is a computer science student”.

Express the statement “some computer science student

must take a discrete mathematics course”.

$x(Q(x) → P(x))

Express the statement “some student must take a discrete

mathematics course or be a computer science student”.

$x(Q(x) ˄ P(x))

EXAMPLES OF USING QUANTIFIERS IN REALITY

Assume:

A(x) :  x is a apple.

B(x) :  x is a banana.

C(x) :  x is cherry.

and the universe of discourse for all three functions is the set of all fruits.

-  Everything is a apple :  "x A(x)

- All apple are banana :   "x [ A(x) → B(x) ]

-Some are banana :  $x B(x)