Introduction to Propositional Logic: Formalization and Reasoning
Understanding formalization in propositional logic involves replacing atomic propositions with propositional variables and natural language connectives with logical connectives. The process abstracts from internal proposition structure, reducing meaning to True or False. The language allows formalizing propositions into molecular forms, using logical connectives like negation, conjunction, disjunction, and implication. Each connective has specific properties and rules, aiding in logical reasoning and analysis of statements.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Formalization and reasoning in propositional logic Introduction to Logical Thinking, Lesson 3 Course Guarantor: Marek Men k Author of the slides: Marie Du 1
Formalization in the PL language As mentioned above, in this language, we can formalize only the way of composing propositions into molecular ones. Atomic propositions are replaced by propositional variables p, q, , and natural language connectives by logical connectives , , , a . For instance, the proposition It is not true that if it is wet then it is raining is formulized by (p q) where it is wet is formalized by pand It is raining by q. In this process, we abstract from any internal structure of the propositions and from any mutual (causal or temporal) relations between them. Their meaning is reduced to True (1) or False (0). Thus, for instance, the proposition It is wet because it is raining is an atomic proposition, as because is not an implication. 2
Formalization in the PL language The negace ( ) connective corresponds to expressions like it is not true that , not , etc. It is an unary connection applied to just one proposition. The conjunction ( ) connective is denoted by expressions like and , but , sometimes only by a comma. It is a commutative connection, which means that (p q) (q p). The symbol is here a meta-symbol expressing the fact that the two formulas are equivalent, i.e., have the same models. Be careful! Not each and in natural language can be analyzed by conjunction. For instance, the following propositions are (from the PL point of view) atomic: Apples and pears got mixed up. I came home and (then) made a fire . The first proposition says that apples and pears got mixed up together. Hence, it is not equivalent to two atomic propositions connected by conjunction Apples got mixed up and Pears got mixed up . In the second case, there are two atomic propositions I came home , I made a fire , but these are not connected by conjunction. If it were so, the whole proposition would be equivalent to I made a fire and (then) came home , which is of no sense. The reason is their temporal relationship: First, I came home and then made a fire. 3
Formalization in the PL language The disjunction ( ) connective corresponds in natural language expressions like or , as the case may be , etc. It is also commutative, hence, (p q) (q p). I will go by train (p) or by bus (q): Disjunction ( ) in the propositional logic is inclusive or. It means that the formula p q is true for the valuation p=1, q=1. I will go by train or bus (or both). If one wants to express an exclusive or, then we should use another connective called alternative; it is negation of equivalence. This man is married (p), or single (q) : (p q) (p q) 4
Formalization in the PL language The implication ( ) connective is denoted by expressions like If, then , when, then , etc. It is the only binary connective that is not commutative; the first proposition is thus called the antecedent, the second consequent. Instead commutativity, there is a law of transpozition: (p q) ( q p) Implication, as all the PL connectives, does not render any relationship between connected propositions. Hence, neither causal nor time sequence is expressed by implication. Therefore, material implication. Natural language connectives that express causality, like because , as , since , do not denote material implication. Example. Since our football team lost (p), the players returned home from the championship earlier then expected (r) . If we analyzed the sentence by p r, it would have to be true also in case that p, i.e. when our team did not loose, which obviously is not true. 5
Formalization in the PL language The equivalence ( )connective is denoted by if and only if , or iff for short, but not by only if or just if . Examples: Greek warriors used to win (p) if and only if the battle had been decided by the fitness of warriors (q). : p q Natural number is divisible by 3 (p) iff the sum of its digits is divisible by 3 (q). : p q Comment.: In natural language, equivalence is not frequently used; rather, it is often used in mathematical definitions statements or statements of other rigorous disciplines. 6
Formalization in the PL language Consider these two propositions: w m a) b) Situation: I did not win. In which case can I get a lot of money? Solution. In case (a) I can make a lot of money though I didn t win, as winning is just a sufficient condition for making money; it is not a necessary one. I might make money in some other way. In case (b) I cannot make a lot of money in any other way, as winning is here a necessary and sufficient condition. You will make a lot of money if you win You will make a lot of money if and only if you win w m 7
Necessary and sufficient condition Natural number is divisible by 3 if it is divisible by 6. d6 d3 Being divisible by 6 is a sufficient condition for being divisible by 3 (but it is not necessary; for instance, numbers divisible by 9 are also divisible by 3). On the other hand, being divisible by 3 is a necessary condition for being divisible by 6. In other words, if a number is not divisible by 3, it is not divisible by 6: d3 d6 You can drive a car (dc) only if you have a driving licence (dl). dc dl Having a driving licence is a necessary condition for driving a car. Hence, if you don t have a driving licence, you cannot drive a car: dl dc 8
Valid arguments in propositional logic Recall. Definition (deductively valid argument) The argument P1, , Pn|= C is deductively valid, if and only if under no circumstance is it possible that all the premises P1, , Pnwere true and the conclusion C false. We also say that the conclusion C logically follows from (is entailed by) the premises P1, , Pn Equivalent definition The argument P1, , Pn|= C is deductively valid, if and only if the assumption of premises being true and the conclusion false yields a contradiction. How can we model those circumstances in propositional logic? Here we have no other possibility but as a combination of truth (1) or falseness (0) of atomic propositions of which a molecular one is composed; hence, by valuations. 9
Valid arguments in propositional logic Definition. Model of a set of PL formulas {F1, , Fn} is such a valuation for which all the formulas F1, , Fn are true. Example. The set of formulas {p q, p, q r} has three models: 1. p = 0, q = 1, r = 1 2. p = 0, q = 1, r = 0 3. p = 0, q = 0, r = 1 Note that a set of formulas has the same models as the conjunction of these formulas. A set of formulas that does not have any model is contradictory, or inconsistent (also not satisfiable). For instance, the set {p q, p, q} is not satisfiable; it has no model. 10
Valid arguments in propositional logic Definition: (logical entailment in PL). Let P1, , Pn, C be PL formulas. Then the formula C is logically entailed by the premises P1, , Pn, i.e. P1, ,Pn|= C, iff C is true in all the models of the set of premises {P1, , Pn}. Corollary 1: The argument P1, ,Pn|= C is deductively valid iff each model of the set {P1, , Pn} is also a model of the formula C. Corollary 2: The argument P1, ,Pn|= C is deductively valid iff the set {P1, , Pn, C} does not have any model, it is not satisfiable. Corollary 3: (semantic theorem of deduction): The argument P1, ,Pn|= C is deductively valid iff the formula (P1 Pn) Z is a tautology. In symbols, P1, , Pn|= Z |= (P1 Pn) Z 11
Semantic proofs; Direct and indirect proof Direct and indirect proof Corollary 1 gives a hint how to apply a direct proof, whereas corollary 2 is a hint for an indirect proof. Example. Consider this argument p q p r r q We are going to prove that the formula r q logically follows from the formulas p q, p r. Let us make both a direct and indirect proof. 12
Direct proof by a truth table Direct proof by a truth table p q, p r |= r q p q 1 1 1 1 1 1 0 0 p r 1 0 1 0 1 1 1 1 r q 1 1 1 0 1 1 1 0 p 1 1 1 1 0 0 0 0 q 1 1 0 0 1 1 0 0 r 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 It suffices to look at those valuations of the variables p, q,r for which both the premises are true, and check whether for these valuations the conclusion is true as well. Hence, we only check the lines 1, 3, 5 and 6. The argument is valid. 13
Indirect proof by a truth table Indirect proof by a truth table p q, p r |= r q p q 1 1 1 1 1 1 0 0 p r 1 0 1 0 1 1 1 1 ( r q) 0 0 0 1 0 0 0 1 p 1 1 1 1 0 0 0 0 q 1 1 0 0 1 1 0 0 r 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 We can see that the set {p q, p r, ( r q)} is contradictory; it does not have any model. There is no valuation for which all the three formulas would be true. 14
Indirect proof of Indirect proof of p q, p r |= r q Propositional logic is a complete and decidable system; everything can be proved by a truth table that is always finite. However, the size of the truth table is growing exponentially with respect to the number of propositional variables. If there are n variables, then the number of lines is 2n. For this reason, we look for more effective methods. Indirect proof. We assume that there is a valuation for which all the premises are true and the conclusion false. Then we show that such a valuation cannot exist, as the assumption yields a contradiction. 15
Indirect proof of Indirect proof of p q, p r |= r q p q, p r | r q a) 1 1 0 b) c) 1 0 d) 1 0 e) 0 the assumption of indirect proof 1 0 contradiction Explanation: Line (b): the implication r q is false only if r=1 and q=0. Line (c): Since q=0 and the disjunction p q is true by assumption, it must be the case that p=1. Line (d): If r=1 then r=0. But according to (c) p=1. Hence the implication p r = 0, which contradicts the assumption. 16
Valid logical scheme Now we can substitute for the variables p, q, r any propositions of natural language, and we obtain a valid argument. For instance, let p = It is Tuesday , q = It is Wednesday , r = Lecture on logic takes place We have got a valid argument It is Tuesday or Wednesday If it is Tuesday, the lecture on logic takes place If the lecture on logic does not take place, it is Wednesday According to Corollary 3, we can derive other valid schemata, for instance, this one: p q p r r q 17
Valid logical scheme By substituting other natural language propositions, we obtain another valid argument: He is at home or went to the pub If he is at home, then he plays piano But he doesn t play piano He went to the pub 18
