002-more on predicate calculus

1 .

2 . Logic - recap ● So far, we have seen that: ● Logic is a “language” which can be used to describe: ● Statements about the real world ● The simplest pieces of data in an automatic processing system such as a computer 

3 . Logic - recap ● The key characteristic of a statement, or a piece of data, in logic is its truth value. There are two possible truth values: ● True ● False 

4 . Logic - recap ● Simple statements, or simple pieces of data, can be joined together to give more complicated structures using logical connectives. ● The most important of these are “and”, “or”, “implies”, “equivalent to” and “not”, for which we use the symbols ∧, ∨, ⇒, ⇔, and ¬ respectively. 

5 . Logic - recap ●Each of these logical connectives is defined by a truth table. ● It is often possible to convert an English sentence into a logical formula – there are simple techniques for doing this. 

6 . Logic - recap ● Questions: ●“when is this formula true?” ● “are these two formulae essentially the same?” ● One useful technique for answering questions about logical formula (such as above) is to draw up a large truth table describing the formula/formulae in question. 

7 . What is low-level logic used for? ● To specify the way in which individual bits of information are processed in order to perform the arithmetic, and all the other forms of symbolic processing, that goes on in the circuits of a computer. 

8 . What is high-level logic used for? ● Used as an unambiguous language, ● i.e. as a medium for knowledge representation. 

9 . What is high-level logic used for? ● Used as a rigorous form of reasoning. ● Deductions which follow the rules of logic are guaranteed to be correct. ● This is not necessarily true of other representation schemes. ● So logic can act as a "gold standard" against which other forms or representation and reasoning can be assessed. 

10 . What is high-level logic used for? ● Logic is available for establishing whether a complicated argument, e.g. a legal case, makes sense or not. 

11 . What is high-level logic used for? ●Logic is a tool for mathematical research. ● The mathematician has available a set of propositions which have been established as true - ● these are referred to as "the axioms". ● He/she has a proposition, or set of propositions, that he/she wants to prove to be true - ● referred to as "the theorem". ● Both sets can be written as statements in logic: ● the problem is to find a set of sound logical manipulations to convert one into the other. 

12 . More on processing logical formulae ● The “build a truth table” technique described earlier always works, ● at least for the simple form of logic we’ve been using so far. ● However, sometimes it isn’t necessary. Instead, to solve a problem in logic, we can use: ● Rules of inference ● Logical equivalencies 

13 . Rules of inference ● These are well-established ways of proving an argument in logic. 

14 . The most useful are: ● modus ponens: P ⇒ Q. P. ∴Q. ● modus tolens: P ⇒ Q. ¬Q. ∴¬P. ● disjunctive syllogism:P ∨ Q. ¬P. ∴Q. ● hypothetical syllogism: P ⇒ Q. Q ⇒ R. ∴P ⇒ R. ● contraposition: P ⇒ Q. ∴¬Q ⇒ ¬P. ● In English, the first of these would read “If you know that P implies Q, and you know that P is true, then you know that Q is true.” ● These can be used to establish the truth of arguments involving complicated formulae. 

15 . Logical equivalences: ● these are well-established ways of turning a logical statement containing one set of logical connectives into a statement containing a different set. 

16 . Logical equivalences ● Here are some of the more important ones. ● Idempotency P is logically equivalent to (P ∧ P) ● Double negation P is logically equivalent to ¬¬P ● Commutative laws (P ∧ Q) is logically equivalent to (Q ∧ P) (P ∨ Q) is logically equivalent to (Q ∨ P) 

17 . Logical equivalencies ● Associative laws (P ∧ (Q ∧ R) is logically equivalent to ((P ∧ Q) ∧ R) (P ∨ (Q ∨ R)) is logically equivalent to ((P ∨ Q) ∨ R) ● Distributive laws (P ∧ (Q ∨ R) is logically equivalent to ((P ∧ Q) ∨ (P ∧ R)) (P ∨ (Q ∧ R)) is logically equivalent to ((P ∨ Q) ∧ (P ∨ R)) 

18 . Logical equivalences ● De Morgan’s laws ¬(P ∧ Q) is logically equivalent to (¬P ∨ ¬Q) ¬(P ∨ Q) is logically equivalent to (¬P ∧ ¬Q) ● Contraposition (P ⇒ Q) is logically equivalent to (¬Q ⇒ ¬P) 

19 . Logical equivalences ● Redefining material conditional as a disjunction or conjunction (P ⇒ Q) is logically equivalent to (¬P ∨ Q) (P ⇒ Q) is logically equivalent to ¬(P ∧ ¬Q) ● Exportation (P ⇒ (Q ⇒ R)) is logically equivalent to ((P ∧ Q) ⇒ R)) 

20 .Logical equivalencies ● It's not necessary to remember the elaborate names, or the exact details of these equivalences. ● It is important to appreciate that, by using one of these equivalences, a logical formula can be turned into a formula which looks quite different, but which actually has exactly the same truth value. 

21 . Tautologies and contradictions • A logical statement which is always true (no matter what values you give to the parts that make it up) is called a tautology. • A statement which is always false is called a contradiction. • All other logical statements are known as contingent statements. 

22 .Tautologies and contradictions ● example: Consider the statement (¬P ⇒ ((P ∨ Q) ⇔ Q)). P could be true and Q could be true. P could be false and Q could be false. P could be true and Q could be false. P could be false and Q could be true. ● In every one of these cases, the whole statement would be true. ● So the statement is a tautology. 

23 .Propositional calculus ● The simple form of logic which we have been using so far, in which the symbols stand for ideas which can be expressed as whole sentences, is known as Propositional Calculus. Calculus 

24 .Propositional calculus ● Propositional calculus is decidable: ● it's always possible to decide whether an argument in propositional calculus is valid or not. ● You can either use the logical equivalence rules, and the rules of inference, described above, or you can build a big truth table. 

25 . Propositional calculus ● Propositional calculus: ● is the simplest form of logic, ● and also the weakest, in terms of its power to express ideas. ● Other forms of logic have been invented to express more complex ideas. 

26 . Predicate calculus ● Another form of logic: first order predicate calculus. ● There are many fairly simple, obvious arguments that propositional calculus cannot handle at all. e.g. All lawyers are scoundrels. Sir James Thames is a lawyer. Therefore Sir James Thames is a scoundrel. 

27 . Predicate calculus ● 1st order predicate calculus has some extra features: the statements joined by the logical connectives can be predicates. e.g. a(b) a(b, c) lawyer(Sir_James_Thames) owes(Jim, Sid, 500pounds) These can convey ideas such as "b is an a", “b has the quality a”, or "b & c are connected by the property a". A predicate can have any number of places, i.e. items in brackets. 

28 . Predicate calculus ● The items inside the brackets of a predicate can be constants (names of things or relationships) or variables. ● If they're variables, they don't refer to specific things; specific items can be substituted for them. ● When this happens, all variables with the same name will refer to the same thing. 

29 .Predicate calculus - the universal quantifier ● 1st order predicate calculus has a symbol ∀ called the universal quantifier. ● ∀x means "for every x".