In this article we will discuss about:- 1. Concept of Proportional Logic 2. Properties of Propositional Logic Statements 3. Tautologies 4. Theorem Proving .
Concept of Proportional Logic:
We now show how logic is used to represent knowledge. The simple form of logic is Propositional Logic, also called Boolean Logic. Facts can be expressed as simple propositions. A proposition is can have one of the two values – True or False. These are known as TRUTH values.
Consider two atomic statements:
A proposition or its negation or a group of statements and/or their negations, connected by certain connectors. When a statement can not be logically broken into smaller statements it is called atomic. It is raining and Dr. A.P.J. Abdul Kalam is the president of India.
ADVERTISEMENTS:
Are propositions whose values (true) T or false (F) depend on the situation or the time.
The first statement may or may not be true now depending upon the weather, the second was true till he laid down his office. A proposition which is true under all circumstances is called tautology. For example, ‘4’ divided by ‘2’ is ‘2’. A proposition which is false under all circumstances is called contradiction. For example, Amritsar is the capital of India.
Actually propositional logic (or propositional calculus or even preposition logic) is a symbolic logic for manipulating propositions.
The word calculus has to do nothing with calculus invented by Newton and Leibnitz. Calculus is a latin word, meaning a little store used for calculus. Statement calculus and sentinal calculus are also used for PL. Statements which cannot be answered absolutely are called open statements e.g. “Garlic tastes wonderful” is an open statement because it is true for some people and not true for others.
ADVERTISEMENTS:
Consider Another Sentence:
She is beautiful, It is open statement because it contains a variable “she”. Truth values cannot be assigned to open sentences until we know the specific person or instance referred to by the variable.
Another difficulty with this so sentence is the meaning of the word “beautiful”. What beautiful; some people think others may not. This ambiguity in the word beautiful can neither be handled by propositional logic nor predicate logical but by Fuzzy logic.
Syntax:
ADVERTISEMENTS:
The syntax of propositional logic defines now allowable sentences are firmed. We will use uppercase names for symbols- P, Q, R etc. which represent propositions and can be true or false they are chosen arbitrary. There are two proposition symbols with fixed meaning. True is always true proposition and False is always false proposition.
Complex sentences are constructed from such simpler sentences using logical connectives. There are five connectors in common use.
¬ (Not):
A sentence such as ¬, P is called negation of P. A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal). It is also written as n.
ADVERTISEMENTS:
∧ (And):
A sentence whose main connective is ∧ such P ∧ Q is called a conjunction; its parts are conjuncts. The ∧ looks like an ‘A’ for ‘AND’.
∨ (or):
A sentence using P ∨ Q is a disjunction of the disjuncts P and Q, its parts as disjuncts. The ∨ comes from Latin word ‘vel’ which means ‘OR’.
ADVERTISEMENTS:
→ (Implies):
A sentence such as (P ∧ Q) → R is called an implication or conditional. Its premise or antecedent is (P ∧ Q) and its conclusion or consequent is R. Implications are also called rules or if… then statements. The implication symbol is also sometimes written as : ⊃
Semantics:
The semantics or meaning of a sentence is just the value true or false. In logic it means that is, an assignment of a truth value to the sentence. The interpretation for a sentence (or group of sentences) is an assignment of a truth value to each prepositional symbol occurring in the sentence.
For finding the true interpretation of a sentence semantic rules are applied repeatedly till the truth value of the sentence is established. Some semantic rules are summarised in table 6.1., using the various connectives relationship between them.
Properties of Propositional Logic Statements:
A statement is a sentence the two terms have been used interchangeably. When a statement cannot be logically broken into smaller statement. It is called atomic.
Satisfiable:
A atomic propositional formula is satisfiable if there is a interpretation for which it is true. In the table 6.1 P v Q is satisfiable for first three propositional formula (statements).
Tautology:
A propositional formula is valid or a tautology it is true for all possible interpretations.
Contradiction:
A propositional formula is contradictory (unsatisfiable) if there is no interpretation for which it is true. For example, Amritsar is the capital of India in table 6.1 P v Q is unsatisfiable for the row 4.
Contingent:
A contingent statement is one which is neither a tautology nor a contradiction.
If a conditional is also a tautology, then it is called an implication and has the symbol ⇒ in place of →. A bi-conditional which is also a tautology is called a logical equivalence or material equivalence symbolized as <=> or ≡. Two statements which are logically equivalent always have the same truth values. For example, p ≡ ~ ~p or even PVQ ≡ QVP (prove it using table 6.1).
Validity and Satisfiability are Connected:
An alternative definition of equivalence is as follows:
P is valid iif ¬ P is unsatisfiable; contra positively, P is satisfiable iff ¬ P is not valid. This leads to a useful result. P |= Q if and if (i if) the sentence (P ^ ¬ Q) is unsatisfiable. (= is called logical entailment. The statement P |= Q means sentence P entails sentence Q. The formal definition of entailment P |= Q; iif P is true, Q is also true. Informally, the truth of Q is contained in the truth of P.
Proving Q from P by checking the unsatisfiability if (P ^ ¬ Q) corresponds exactly to the standard mathematical proof technique of reduction and absurdum (reduction to an absurd thing). It is also called proof by refutation or proof by contradiction. We assume a sentence to be false and show that this leads to a contradiction with known axioms. This principle is used in Resolution.
A valid statement is satisfiable and a contradictory statement is invalid. The converse may not be necessarily true.
In support of the above definitions consider the following statement:
P is satisfiable but not valid since an interpretation which assigns false to P assigns false to sentence P.
P V ~ P is valid since every interpretation results in a value of true (P ^ ~ F) is contradiction.
Since every interpretation results in a value of false for (P ^ ~ ~ P).
P and ~ (~P) are equivalent since each has the same truth values under every interpretation.
P is a logical consequence of (P ^ Q) since every interpretation for which (P ^ Q) is true, P is also true.
The concept of logical consequence is useful in the sense that it provides propositional logic the basis for inferencing.
Table 6.2., gives some of the important laws of logical equivalence. They play the same role in logic as arithmetic identities do in ordinary mathematics.
A proposition is statement or its negation—or a group of statements and/or their negations, connected by AND, OR and If-Then operators.
For instance,
P’
it-is-hot, the-sky-is-cloudy,
it-is-hot ^ the-sky-is-cloudy,
it-is-hot → the-sky-is-cloudy
are all examples of propositions and p, q, the-sky-is-cloudy’, are examples of atomic propositions.
A proposition can assume a binary valuation space., i.e., for a proposition p, its valuation space, ∨ (p) ϵ {0, 1}
Let r be a propositional formula, constructed by connecting atomic propositions p, q, s, etc. by operators. An interpretation for r is a function which maps ∨ (p) ∨ (q) and ∨ (s) into true or false values that together keep r true.
For example, given the formula p ^ q, The possible interpretation is ∨ (p) = true and ∨ (q) = true. It may be noted that for any other values of p and q the formula is false.
There may be more than one interpretation of a formula.
For instance, the formula:
¬ p ∨ q has three interpretations given below:
Interpretations:
{∨ (p) = true, ∨ (q) = true}, (∨ (p) = false, ∨ {q) = false}, and
{∨ (p) = false, ∨ (q) = true}. The reader should verify the truth value of the formula for the fourth possibility.
The propositional formula p ∨ q is satisfiable as it is true for some interpretations {∨(p) = true, ∨(q) = true}, {∨(p) = false, ∨(q) = true} and {∨(p) = true, ∨(q) = false}, ∨ (proposition) represents valuation space of the proposition. Generally, we write |= p to denote that p is satisfiable.
The reader can show that (p ^ q) ^ r ≡ p ^ (q ^ r) is a tautology, since it is true for all possible ∨(p), ∨(q) and ∨(r) ɛ {0, 1}. Here we have 8 possible interpretations for the propositional formula, for which it is true. Try those values.
The relationship of all formulas, and satisfiable and valid formulas is presented in Venn diagram 6.3.
Tautologies in Propositional Logic:
The tautologies may be directly used for reasoning in propositional logic.
For example, consider the following statements:
P1 = the-sky-is-cloudy, p2 = it-will-rain, and p3 = if (the-sky-is-cloudy) then (it- will-rain) ≡ p1 → p2
“p1” and “p2” above represents premise and conclusion respectively for the if then clause. It is obvious from common sense that p, directly follows from p 1 and p3. However to prove it automatically by a computer, one requires help of the following tautology, the proof of which is also given here.
P3 ≡ p1 → p2
≡ ¬ (p1 ^ ¬ p,), since p1 true and p2 false cannot occur together for ∧.
≡ ¬ p1 v p2 (by De Morgan’s law).
However to prove p1 from p2 and p we have to wait till example. Till-then let us study the list of tautologies.
Table 6.2. List of tautologies in propositional logic.
Theorem Proving in Propositional Logic:
We present here two techniques for logical theorem proving in propositional logic.
These are:
1. Semantic, and
2. Syntactic methods of theorem proving.
1. Semantic Method:
The following notation will be used to represented a symbolic theorem, stating that conclusion “c” follows from a set of premises p1, p2…pn
In this technique, we first construct a truth table representing the relationship of p1 to pn with “c”. Then we test the validity of the theorem by checking whether both the forward and backward chaining methods to be presented shortly an hold good. The concept can be best illustrated with the example.
Example 1:
Let us redefine p = the-sky-is-cloudy, q = it-will-rain and r ≡ p → to be three propositions.
We now form a truth table of p, q and r, and then attempt to check whether forward and backward cleaning holds good for the following theorem:
Forward Chaining:
When all the premises are true, check whether the conclusion is true. Under this circumstance, we say that forward chaining holds good. i.e. from data to goat.
When p and r are true i.e. all premises are true the goal (q) should also be true for holding the forward chaining. In the row 4, all promises (p = 1, and r = 1) are true and also goal (q = 1) is true, i.e. chaining from data (premise) goal can be derived or forward chaining holds good. So, forward chaining holds good. Now, we test for backward chaining.
Backward Chaining:
When all the consequences are false, check whether at least one of the premises is false, i.e., from goal to data.
In this example q = 0 in the first and third row. Note that when q = 0, then p = 0 in the first row and r = 0 in the third row. So, backward chaining holds good.
As forward and backward chaining both are satisfied together, the theorem: p, r => q is a tautology.
Example 2:
Show that for example (1 ),q, r = ≠> p.
It is clear from the truth table 6.2 that when p = 0, then q = 0 (first row) and r = 1 (first row), backward chaining holds good. But when q = r = 1, p = 0 (second row), forward chaining fails. Therefore, the theorem does not hold good.
2. Syntactic Methods:
Before presenting the syntactic methods for theorem proving in propositional logic, we state a few well-known theorems.
Standard theorems in propositional logic:
Assuming p, q and r to be proposition, the list of the standard theorems is presented below:
The syntactic approach for theorem proving can be done in two ways, namely:
(i) By the method of substitution and
(ii) By Wang’s algorithm.
(i) Method of Substitution:
By this method, left-hand side (or right-hand side) of the statement to be proved is chosen and the standard formulas, presented above, are applied selectively to prove the other side of the statement.
Example:
Prove the contraposition theorem (15).
The contraposition theorem can be stated as follows. When p and q are two propositions, the theorem takes the form of p → q ⇔ ¬ q → ¬ p
Analogously, starting with the R.H.S., we can easily reach the L.H.S. Hence, the theorem bi-directionally holds good.
Example:
Prove theorem (14) by method of substitution.
Analogously, the L.H.S. can be equally proved from the R.H.S. Hence, the theorem follows bi-directionality.
(ii) Wang’s Algorithm:
Any theorem of propositional logic is often represented in the following form:
where pi and qi. represent propositions. The comma in the L.H.S. represents AND operator, while that in the R.H.S. represents OR operator.
Writing the theorem in symbol form:
This kind of theorem can be easily proved using Wang’s algorithm.
The algorithm is formally presented below:
Wang’s Algorithm:
Begin:
Step I: Starting Condition:
Represent all sentences, involving only ∧, ∨ and ¬ operators.
Step II: Recursive Procedure:
Repeat steps (a), (b) or (c) whichever is appropriate until the stopping condition, presented in step III, occurs.
(a) Negation Removal:
In case negated term is present at any side (separated by comma) bring it to the other side of implication symbol without its negation symbol.
(b) AND, OR Removal:
If the L.H.S. contains ∧ operator, replace it by a comma. On the other hand if R.H.S. contains ∨ operator, also replace it by a comma.
(c) Theorem splitting:
If the L.H.S. contains OR operator, then split the theorem into two sub-theorems by replacing the OR operator. Alternatively, if the R.H.S. contains AND operator then also split the theorem into two sub-theorems.
Step III: S Topping Condition:
Stop theorem proving process if either of (a) or (b), listed below, occurs:
(a) If both L.H.S. and R.H.S. contain common atomic terms, then stop.
(b) If L.H.S. and R.H.S. have been represented as a collection of atomic terms, separated by commas only and there exist no common terms on both sides, then stop End.
In case all the sub-theorems are stopped, satisfying condition III (a) or (b), then the theorem holds good. We would construct a tree structures to prove theorems using Wang’s algorithm. The tree structure is necessary to break each theorem into sub- theorems.
Example:
Prove the chaining rule with Modus Ponens using Wang’s algorithm.
Proof:
The chaining rule with Modus Ponens can be described as:
where p, q and r are propositions (atomic).
We now construct the tree. A node in the tree denotes one propositional expression. An arc in the tree denotes the step of Wang’s algorithm, which is applied to produce the next step. The underlined symbols in both the left and right-hand side of the implication symbol describe the termination of the sub-tree by step III (a).
Since all the terminals of the tree have been stopped by using III (a), the theorem holds good.
Exercise:
For any three clauses p, q and r.
Prove:
The above theorem, which can be proved by Wang’s algorithm, is left as an exercise for the students.