Introduction to Formalization and Valid Reasoning in Logic
Understanding the need for formalizing natural language in logic to eliminate ambiguities and vagueness. Exploring valid forms of reasoning and how logical rules help in automating correct arguments. Introducing propositional and predicate logic systems with examples of valid arguments.
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
Knowledge Formalization; Language and semantics of propositional logic Introduction to Logical Thinking, Lesson 2 Course Guarantor: Marek Men k Author of the slides: Marie Du 1
Why do we need to formalise? Natural language is rich; yet it suffers from a lot of ambiguities and vagueness. Hence, we need to introduce an unambiguous formal language in which it would be possible to prove and automatize correct arguments. Moreover, valid arguments share their valid logical forms; it is useful to record such forms in a formal language so that these can be applied whenever possible. We have introduced a few simple valid forms of reasoning like, for instance, these: If A, then B; A is true. Hence, B is true as well. If A, then B; B is false. Hence, A is false as well. All P are Q; a is a P. Hence, a is also a Q. All P are Q; a is not a Q. Hence, a is not a P. 2
Valid forms of reasoning Our goal is to fix valid forms of reasoning as valid rules. Whenever we discover an argument with the same valid form, we do not have to prove it anymore, as we know that it is valid. For instance, if we substitute for the symbols A, B (see the previous slide) propositions It is raining and I ll take an umbrella , we obtain valid arguments: If it is raining, I ll take an umbrella; It is raining. Hence, I ll take an umbrella. If it is raining, I ll take an umbrella; I won t take an umbrella. Hence, it is not raining. 3
Valid forms of reasoning Similarly, if we substitute for the symbols P and Q the properties of being a prime number greater than 2 and odd , we again obtain valid arguments: All the prime numbers greater than 2 are odd; 5 is a prime number greater than 2. Hence, 5 is an odd number. All the prime numbers greater than 2 are odd; 6 is not an odd number. Hence, 6 is not aprime number greater than 2. 4
Valid forms of reasoning First, we are going to introduce the simplest logical system, namely propositional logic. Then we extend this system to the 1st-order predicate logic. There are two kinds of valid schemata that we introduced above. 1. The schemata of the first type are, for instance, these: If A, then B; A is true. Hence, B is true as well. If A, then B; B is false. Hence, A is false as well. A or B. But B is false. Hence, A is true. Here we can substitute propositions for the symbols A, B to obtain valid arguments that are a subject of propositional logic. 2. The second type of schemas are, for instance these: All P are Q; a is a P. Hence, a is also a Q. All P are Q; a is not a Q. Hence, a is not a P. Here we can substitute predicates (denoting properties) for the symbols P, Q; these properties are possessed by some or all the elements of a given domain of interest. These argument are a subject of the 1st order predicate logic. 5
The language of propositional logic Reasoning in propositional logic is based only on composing atomic propositions into molecular propositions by means of logical connectives. Terms denoting logical connectives are, for instance: If , then , when , then , only if , and , or , but , neither nor , etc. Hence, we need two types of symbols. 1. The symbols standing for atomic propositions such as It is raining , John goes home , etc., are propositional variables p, q, r, 2. The symbols standing forlogical connectives are: implication ( If then ), conjunction ( and ), disjunction ( or ), equivalence ( if and only if ). Negation is also a connective though it just negates one proposition. Propositions of this logic are reduced to their truth-values, True (1) or False (0). When composing these propositions by logical connectives, no causal or temporal relations play any role. Propositional logic = algebra of truth values 6
The language of propositional logic For instance, the proposition If the Earth is flat, then 1+1=2 is true in propositional logic. It is so because the connective if then denotes the so-called material implication that is false only if the antecedent (on the left) is true and the consequent (on the right) is false. Hence, false implies true is true. Propositional connectives are truth-value functions, the arguments and values of which are True (1) and False (0). These functions are usually defined by a truth table. Before we define them, we need to say something about the notion of a function. 7
The notion of a function (Total) function f is a mapping from the set A into the set B that associates each element of A with just one element of B. The set A is called a domain of the function f and B codomain of f. Notation: f: A B. The domain of a function can be the set of ordered pairs, triples, generally n-tuples of elements of the sets A1, , An. Such a set of all ordered n-tuples is called Cartesian product of the sets A1, , An, denoted as A1 An. Note. Cartesian product is not commutative. 8
The notion of a function For instance, the binary function of adding on the set of natural numbers N is the mapping from the set N N of all pairs of natural numbers to the set N. Hence, +: N N N. This function is illustrated by a table: Arguments Values 0 0 0 1 0 1 0 1 1 1 1 2 2 0 2 0 2 2 2 1 3 9
Binary connectives as truth-value functions Denoting the set of truth values True and False by {1, 0}, the truth-value functions are mappings of the type {1, 0} {1, 0} {1, 0}. By a simple combinatoric consideration, we can see that there are 16 binary truth-value functions. From these 16 functions, the most frequently used are the functions denoted by the binary connectives implication ( ), equivalence ( ), disjunction ( ) and conjunction ( ). 10
truth-value functions Definition of binary connectives, i.e. truth-value functions is usually provided by a table: p q p q p q p q p q 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 11
truth-value functions Example. Let the propositional variable p stand for the atomic proposition The Earth is flat and the variable q for 1+1=2 . Then the following composed propositions are formalized as follows: p q p q p q p q If the Earth is flat, then 1+1=2 The Earth is flat or 1+1=2 The Earth is flat and 1+1=2 The Earth is flat if and only if 1+1=2 12
Negation Note that the expressions it is not true that , not which negate the truth of a proposition, also makes from an atomic proposition molecular one, as a molecular proposition is such that there is a proper part of it that is a proposition. This connective is called (Boolean) negation, denoted as . For instance, the proposition The Earth is not flat is formalized by p. It is obvious that p is true iff p is false and vice versa. Propositional logic keeps the tertium non datum principle. It means that all the propositions can be only true or false (two truth values). Note. There are other non-classical logics that deal with three or even four truth values, or even with the interval 0,1 of truth values, which are the so- called fuzzy logics. However, in this course we deal only with classical two- value logic. 13
Notation for binary connectives Notational conventions for propositional connectives are not unique in literature. Sometimes, alternative symbols are used: Symbol Alternative & , , ~ 14
The language of propositional logic In general, language is a potentially, countably infinite set of well- formed expressions that we call here formulas. If we want to define a potentially infinite set, then we usually apply an inductive definition. First, the alphabet of the language is defined. It is the set of basic symbols of which formulas can be formed. Second, the grammar of the language is defined. Grammar inductively specifies or generates an infinite set of well-formed formulas (WFF). 15
The language of propositional logic: inductive definition I) Alphabet of the PL language is the set of the following symbols: Propositional variables: p, q, r, ... (possibly with subscripts) Symbols of logical connectives: , , , , Auxiliary symbols: (, ), [,],{,} II)Grammar of the PL language: Propositional variables are well-formed formulas.(the base of the definition) If the expressions A, B are well-formed formulas, then the expressions ( A), (A B), (A B), (A B), (A B) are well-formed formulas. (inductive step) Nothing else is a well-formed formula. (closure of the definition) 16
Language of propositional logic The PL language is the set of well-formed formulas of propositional logic. Formulas according to the item (I) are elementary (atomic) formulas, those according to the item (II) are composed (molecular) formulas. Comments: The symbols A, B used in the inductive step of the definition are not formulas; they are meta-symbols serving for denoting any formula. Atomic formulas, i.e. propositional variables stand for simple atomic propositions (more precisely, for their truth values), while composed formulas for molecular propositions. Proposition is atomic, if none of its proper parts is a proposition. For instance, it is raining is an atomic proposition while It is not raining is a molecular proposition. Or, It is not raining and sunshine is also a molecular one. 17
Language of propositional logic; comments Using parentheses in the formulas can be reduced by the following conventions: The outermost parentheses can be omitted. Logical connectives are ordered by their priorities: , , , , . Hence, negation is of the highest priority, etc. If priorities do not unambiguously determine the evaluation, the formula is evaluated from left to right. For instance, p q r s is understood as if it were written like this: (((p q) r) s). Mind! This priority convention should not be overused; it is better to use the parentheses to make the structure of the formula clear. Since conjunction and disjunction are associative and commutative, parentheses can be omitted. For instance, instead of ((p q) r) or (p (q r)) we can simply write p q r. Be careful! Implication is neither associative nor commutative; hence, parentheses cannot be omitted. For instance, the formulas A = (p (q r)), B = ((p q) r) are not equivalent. It is easy to check by a truth table. The formula A is true for p = 0, regardless of the values of q and r. Formula B is not true for p = 0 and r = 0. 18
Semantics (meaning) of PL formulas Semantics of a molecular formula is determined by the truth values of its atomic sub-formulas, and by the way of their composing. For instance, the formula p q is true, if at least one of the propositions p, q is true, otherwise false. The formula p q is true, if both the propositions p, q are true, otherwise false. When evaluating the truth value of a composed formula, we must account for all the possible assignments of truth values 0, 1 to propositional variables occurring in the formula. These assignments (hence functions) are called valuations v: {p, q, r, } {0,1} The way of evaluating the truth value of a molecular formula for particular valuations v is again best demonstrated by a truth table. 19
Semantics (meaning) of PL formulas Example. Consider the formula ( p q). To evaluate it for its truth values in particular valuations v, we make a table. p 0 ( p q) 0 p q The formula is true for these two valuations: p=1, q=0 and p=0, q=1. Valuations v, at which a given formula is true, are called its models. The formula that has at least one model is satisfiable. 1 1 1 0 0 1 0 1 1 1 0 0 1 0 20
Tautology vs. contradiction Formula that is true for all the valuations of its propositional variables is called a tautology. Examples of simple tautologies are the propositions It is raining or not , hence the formula p p, or If it is raining then it is raining , hence the formula p p. Example. The formula ( p q) (p q) is a tautology (De Morgan law): p q ( p q) (p q) ( p q) (p q) p q 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 21
Tautology vs. contradiction The opposite of a tautology is a contradiction that cannot be true for any valuation; hence contradiction does not have any model. A typical simple example is the formula (p p). Negation of a tautology is a contradiction, and vice versa. Hence, the formula [( p q) (p q)] is a contradiction because it is negation of a tautology. 22
Summary of the most important notions Valuation is a function {p, q, r, } {0,1}, that associates each propositional variable with a truth value. Model of a PL formula F is such a valuation at which the formula F has the value (1). A formula is satisfiable if it has at least one model. A formula is a tautology (also said logically true), if each valuation is its model. A formula is a contradiction (i.e. non-satisfiable), if it has no model. 23
