 Modern Logic

## What is this Tutorial About?

This tutorial expands on the material covered in Compound Indication by looking at it from the perspective of Modern Logic. Modern logic offers a more systematic and comprehensive analysis of clauses (or propositions) and how atomic propositions can combine to form compound ones. This, however, is a very brief overview and presents only the major discussions.

## Propositional Logic

### Propositions & Their Negations

A proposition is a complete thought which is either true or false. It cannot be both true and false, nor can it be neither. In Arabic, a proposition is termed قضية حملية. Propositions are represented with capital letters, as in the following example.

P

The proposition P: “it is raining today”

A proposition can be negated using the symbol of negation, as in the following example.

¬P

“it is not raining today”

### Combining Propositions Using Logical Connectives To Form Compound Propositions

Two or more propositions can be combined to form another (more compound) proposition.  For example, “it is raining today” and “I’m getting wet” can be combined to form a new statement. We can say, for instance, “it is raining today and I’m getting wet,” or “I’m getting wet because it’s raining today,” and so forth. A compound proposition, in Arabic, is termed قضية شرطية.

There are two main ways in which we can combine propositions (and their negations); conjunction and disjunction. These are summarized in the table below.

 Name Symbol Explanation Conjunction AND P ∧ Q The compound proposition is true only when both P and Q are true Disjunction OR P ∨ Q The compound proposition is true when both P and Q are true, or when either one is true

Consider the two propositions “it is raining today” and “I’m getting wet.” The compound proposition P Q, “it is raining today and I’m getting wet” is true only when it is true that it is raining today and it is true that I’m getting wet. Similarly, the compound proposition P Q, “it is raining today or I’m getting wet” is true when it is both raining today and I’m getting wet, it is raining today but I’m not getting wet, or it is not raining today but I’m still getting wet.

Some further examples appear in the table below. Let P represent the statement “I studied for the test,” and let Q represent the statement “I failed the test.”

 Formula Explanation ¬P ∧ Q I didn’t study for the test, and I failed the test ¬Q ∨ ¬P Either I passed the test, or I didn’t study for it (P ∧¬Q) ∨ (¬P ∧ Q) I studied for the test and I passed it, or I didn’t study for it and I failed it

Notice that Q  is internally negated; failing a test is the opposite or negation of passing it. So when we negate Q, “I didn’t fail the test”, we end up with an affirmative proposition, “I passed the test.” When a statement is internally negated like this, it is termed معدولة in Arabic.

The combination of negation and the logical connectives of conjunction and disjunction  form a set of three manipulations. These three manipulations are enough to represent any and all propositions that can ever be conceived. However, it is sometimes useful and natural to have more complex logical connectives. Below is a table that extends the basic connectives to introduce new ones.

 Name Symbol Equivalent To Explanation Basic Set NOT ¬P negation of P AND P ∧ Q true only when both P and Q are true OR P ∨ Q true when one or both of P and Q is true Other Useful Connectives NAND P ↑ Q ¬ (P ∧ Q) it is not the case that P and Q are both true NOR P ↓ Q ¬ (P ∨ Q) neither is P true, nor is Q true XOR P ⊕ Q (P ∧¬Q) ∨ (¬P ∧Q) true when only one of P or Q is true IMPL P → Q ¬P ∨ Q if P then Q XNOR P ↔ Q (P → Q) ∧ (Q → P) if P, and only if P, then Q

Some examples of the complex connectives are given below. Let P represent the statement “I studied for the test,” and let Q represent the statement “I failed the test.”

 Formula Explanation P ↑ Q it is not the case that I studied for the test and failed it P ↓ Q I didn’t study for the test but I passed it P ↔ ¬Q I passed the test only if I studied for it

### Logical Equivalence

It is important to be able to determine when two logical propositions are equivalent to one another. For example, how can we be sure that P Q is the same as ¬P Q? To give a concrete example, how can we be sure that the following two propositions are equivalent: “if God exists then he is good” and “either God doesn’t exist, or he is good.”

There are two ways to compare propositions. The first is by using their truth tables. A truth table is a chart in which we have all possible combinations of truth and falsehood for our propositions (4 in the case of 2 propositions), and we calculate the resulting truth or falsehood of the compound proposition. For example, in order to write a truth table for P Q, we would start as follows.

 P Q P → Q true true true false false true false false

Then we calculate the truth value of the compound proposition, as follows.

 P Q P → Q true true true true false false false true true false false true

What we are saying here is that, for example:

·         if it is indeed raining today, and I am indeed getting wet, then “if it is raining today then I’m getting wet” is a true statement

·         if it is indeed raining today, but I am not getting wet, then “if it is raining today then I’m getting wet” is a false statement

·         if it is not raining today, but I am indeed getting wet, then “if it is raining today then I’m getting wet” is still true. This is because it’s not even raining today so who’s to say that the statement is false?

·         if it is not raining today, and I am not getting wet, then “if it is raining today then I’m getting wet” is still true. This is because it’s not even raining today so who’s to say that the statement is false?

Now the truth table for ¬P Q is as follows.

 P Q ¬P ¬P ∨ Q true true false true true false false false false true true true false false true true

Notice that the truth column for P Q is exactly the same as that of ¬P Q. This proves that the two logical propositions are equivalent. Whenever one is true, the other is also true, and whenever one is false, the other is also false.

The other way to show that two propositions are equivalent is through the equivalence rules. This is by far the more powerful technique in showing equivalence between two or more propositions. The popular rules are summarized in the table below.

 is equivalent to Example ¬¬P P it is not the case that it is not rainingit is raining P ∧ Q Q ∧ P it is raining and I am wetI am wet and it is raining P ∨ Q Q ∨ P I am on land or I am drowningI am drowning or I am on land (P ∧ Q) ∧ R P ∧ (Q ∧ R) I studied and wrote the test, and I passedI studied, and I wrote the test and passed (P ∨ Q) ∨ R P ∨ (Q ∨ R) either the sun or the moon is out, or it’s pitch blackthe sun is out, or either the moon is out or it’s pitch black P ∧ (Q ∨ R) (P ∧ Q) ∨ (P ∧ R) I wrote the test, and I used either a pen or a pencilI wrote the test and used a pen, or I wrote the test and used a pencil P ∨ (Q ∧ R) (P ∨ Q) ∧ (P ∨ R) either I’m working, or I’m sick and tiredI’m working or I’m sick, and I’m working or I’m tired ¬(P ∨ Q) ¬P ∧¬Q it is not the case that either I passed the test or I failed itI didn’t pass the test nor did I fail it (i.e. I didn’t write it) ¬(P ∧ Q) ¬P ∨¬Q it is not the case that I studied for the test and passed iteither I didn’t study for it or I didn’t pass it (or both) P ∨¬P always true either it’s raining or it’s notnote: propositions that are always true are called tautologies P ∧¬P always false it’s raining and it’s not rainingnote: propositions that are always false are called contradictions P ∨P P it is cloudy or it’s cloudyit is cloudy P ∧P P I am tired and I am tiredI am tired P → Q ¬P ∨ Q if the sun is out then the day is presenteither the sun is not out or (if it is) the day is present

As an example, let’s show that the following two propositions are equivalent: “if God exists and he has no beginning, then he has no end,” and “if God exists and he has an end, then he has a beginning.” We are going to show that if you believe one of these, then you believe both of them because they are logically equivalent.

P: God exists

Q: God has a beginning

R: God has an end

Then we construct the first proposition as follows:

(P ¬Q) ¬R

if God exists and he has no beginning, then he has no end

And the second as follows:

(P R) Q

if God exists and he has an end, then he has a beginning

Now we use the equivalence laws to show that the two propositions are equivalent:

 (P ∧¬Q) → ¬R ⇒ ¬(P ∧¬Q) ∨ ¬R ⇒ ¬((P ∧¬Q) ∧ R) ⇒ ¬(P ∧¬Q ∧ R) ⇒ ¬(P ∧ R ∧¬Q) ⇒ ¬((P ∧ R) ∧¬Q) ⇒ ¬(P ∧ R) ∨Q ⇒ (P ∧ R) → Q

## Predicate Logic

A predicate is a generalized proposition that has the capacity to take one or more parameters. It uses these parameters and substitutes them for components of the sentence. For instance, P “Zaid hit Amr” is a proposition, but P(x)x hit Amr” or P(x, y)x hit y” or P(x, y, t)x hit y at time t” are all predicates. We can say that propositions, then, are special types of predicates that take no parameters. Parameters are usually represented with lower case letters.

Because predicates take parameters, we can add quantification. Predicates can be quantified in two ways; universally or existentially. A universal quantification asserts that the predicate is true for all possible values of a parameter. And an existential quantification asserts that the predicate is true for at least one value of a parameter. For example, let P(x) represent the statement “x hit Amr.” We can then say: for all x, P(x). This means that for all people x, x hit Amr. Or more simply, everyone hit Amr. As a further example, we can say: there exists an x such that ¬P(x). This means that there is someone who did not hit Amr.

A universally quantified statement is known, in Arabic, as a موجبة كلية or a سالبة كلية, depending on the affirmation. And an existentially quantified statement is called a موجبة جزئية or a سالبة جزئية. Below is a chart that summarizes these concepts. Let P(x) represent “x hit Amr,” let Q(x) represent “x is upset,” and let R(x, y) represent “x likes y.”

 Symbol Example Universal (all) ∀ ∀x (¬P(x) → Q(x))everyone who didn’t hit Amr is upset Existential (exists) ∃ ¬∀x∃y R(x, y)it is not the case that everyone has someone who likes them

Notice that the logical relationships of AND, OR, IMPL, etc can be applied to quantified predicates just as they can apply to non-quantified predicates as well as propositions. Notice also that negation can be applied to a quantifier.

When negation is applied to a quantifier, we can simplify the expression by pushing the negation into the scope of the quantifier. When we do this, we must flip the quantifier; universal becomes existential and existential becomes universal. This is summarized in the table below.

 Original Negation Pushed In ¬∀x P(x) ∃x ¬P(x) ¬∃x P(x) ∀x ¬P(x)

An example can illustrate this process more clearly.

 Original Negation Pushed In it is not the case that every human is good there are some humans that are not good it is not the case that some vegetables are good all vegetables are not good

This process is reversible as well. If the entire predicate in the scope of a quantifier is negated, we can pull the negation in front of the quantifier provided we flip the quantifier. The table below demonstrates this.

 Original Negation Pushed In ∃x ¬P(x) ¬∀x P(x) ∀x ¬P(x) ¬∃x P(x)

As an exercise, let’s formalize the theory of cause and effect using predicate logic. Let O(x) represent the statement “event x has occurred,” and let C(x, y) represent the statement “event x was caused by event y.” Then:

fg (O(f) (C(f, g) O(g))

• Proceed to the next lesson: Indicated Assent
• 