0.3 Discrete structures logic  (Page 11/23)

The first row in the rightmost column results since P is false, and the others in that column follow since (P ⋁ Q) is true.

The rightmost column shows that P → (P ⋁ Q) is always true.

2. Some of the implications can also be proven by using identities and implications that have already been proven.

For example suppose that the identity "exportation":

[(X ⋀Y) →Z] ⇔[X →(Y→Z)],

and the implication "hypothetical syllogism":

[(P→Q) ⋀(Q→R)] ⇒(P→R)

have been proven. Then the implication No. 7:

(P→Q) ⇒[(Q→R)→(P→R)]

can be proven by applying the "exportation" to the "hypothetical syllogism" as follows:

Consider (P→Q) , (Q→R) , and (P→R) in the "hypothetical syllogism" as X, Y and Z of the "exportation", respectively.

Then since [ (X ⋀Y )→Z ] ⇔[ X→( Y→Z ) ]implies [ ( X ⋀Y )→Z ] ⇒[ X→(Y→Z ) ], the implication of No. 7 follows.

Similarly the modus ponens (implication No. 3) can be proven as follows:

Noting that ( P→Q ) ⇔( ¬P ⋁Q ) ,

P ⋀( P→Q )

⇔P ⋀( ¬P ⋁Q )

⇔( P ⋀¬P ) ⋁( P ⋀Q ) --- by the distributive law

⇔F ⋁( P ⋀Q )

⇔( P ⋀Q )

⇒Q

Also the exportation (identity No. 20), ( P→( Q→R ) ) ⇔ ( P ⋀Q )→R ) can be proven using identities as follows:

( P→( Q→R ) ) ⇔ ¬P ⋁( Q→R )

⇔ ¬P ⋁( ¬Q ⋁R )

⇔ ( ¬P ⋁¬Q ) ⋁R

⇔ ¬( P ⋀Q ) ⋁R

⇔ ( P ⋀Q )→R

3. Some of them can be proven by noting that a proposition in an implication can be replaced by an equivalent proposition without affecting its value.

For example by substituting ( ¬Q→¬P ) for ( P→Q ) , since they are equivalent being contrapositive to each other, modus tollens (the implication No. 4): [ ( P→Q ) ⋀¬Q ] ⇒ ¬P , reduces to the modus ponens: [ X ⋀( X→Y ) ]⇒Y. Hence if the modus ponens and the "contrapositive" in the "Identities" have been proven, then the modus tollens follows from them.

Predicate logic

Introduction to predicate logic

The propositional logic is not powerful enough to represent all types of assertions that are used in computer science and mathematics, or to express certain types of relationship between propositions such as equivalence.

For example, the assertion "x is greater than 1", where x is a variable, is not a proposition because you can not tell whether it is true or false unless you know the value of x. Thus the propositional logic can not deal with such sentences. However, such assertions appear quite often in mathematics and we want to do inferencing on those assertions.

Also the pattern involved in the following logical equivalences can not be captured by the propositional logic:

"Not all birds fly" is equivalent to "Some birds don't fly".

"Not all integers are even" is equivalent to "Some integers are not even".

"Not all cars are expensive" is equivalent to "Some cars are not expensive",

... .

Each of those propositions is treated independently of the others in propositional logic. For example, if P represents "Not all birds fly" and Q represents "Some integers are not even", then there is no mechanism in propositional logic to find out tha P is equivalent to Q. Hence to be used in inferencing, each of these equivalences must be listed individually rather than dealing with a general formula that covers all these equivalences collectively and instantiating it as they become necessary, if only propositional logic is used.