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.
More Advanced Connectives
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 raining it is raining |
P ∧ Q | Q ∧ P | it is raining and I am wet I am wet and it is raining |
P ∨ Q | Q ∨ P | I am on land or I am drowning I am drowning or I am on land |
(P ∧ Q) ∧ R | P ∧ (Q ∧ R) | I studied and wrote the test, and I passed I 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 black the 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 pencil I 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 tired I’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 it I 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 it either 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 not note: propositions that are always true are called tautologies |
P ∧¬P | always false | it’s raining and it’s not raining note: propositions that are always false are called contradictions |
P ∨P | P | it is cloudy or it’s cloudy it is cloudy |
P ∧P | P | I am tired and I am tired I am tired |
P → Q | ¬P ∨ Q | if the sun is out then the day is present either 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.
In order to do this, let’s start with the following propositions:
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:
∀f∃g (O(f) → (C(f,
g) ∧ O(g))