* Logic: Language and Information 1 ⊃, ∨, ∧, ¬, ≡, ≠, ∀, ∃, λ, ≤, ≥, ∈, ∉, ∞,
- Connectives (կապեր)
- Conjuction
- p & q
- p and q
- or - inclusive Disjunction v (vel in Latin)
- p v q
- inclusive “I’ll get wet, or I’m lucky (and maybe both)’
- exclusive “I’ll get wet, or I’m lucky (and not both)”
- Negation
if p is propostion, its negation is ~p
p is said to be the negand of ~p
- ~p
- !p
- not p
- Conditionals
We say p is the antecedent, and q is the consequent
- if p then q
- if p, q
- q if p
- p only if q
- p implies q (ենթադրել)
- unless
- biconditional if-only-if (iff) p=q p and q are the left-and right-hand expressions of the biconditional
- that
- because
- Conjuction
- Գտնենք կապերը
- Ստեղծել բառարան
- Գտնել ձևերը
- Տրամաբանական կապերի ճշմարտության աղյուսակները
- Ժխտմանը
Եթե ունենք Ա ասույթ, ապա ~Ա բանաձևի ճշմարտության աղյուսակը, որը
ցույց է տալիս ~Ա բանաձևի «ճիշտ» կամ «սխալ» լինելը կախված Ա ասույթի
«ճիշտ» կամ «սխալ» լինելուց, հետևյալն է՝
A ~A 0 1 1 0 - տրամաբանական և կամ Կոնյուկցիա
կոմուտատիվ է
A B (A & B) 0 0 0 0 1 0 1 0 0 1 1 1 - տրամաբանական կամ կամ Դիսյուկցիա դուալ է կոնյուկցիայի նկատմամբ կոմուտատիվ է
- Ժխտմանը
Եթե ունենք Ա ասույթ, ապա ~Ա բանաձևի ճշմարտության աղյուսակը, որը
ցույց է տալիս ~Ա բանաձևի «ճիշտ» կամ «սխալ» լինելը կախված Ա ասույթի
«ճիշտ» կամ «սխալ» լինելուց, հետևյալն է՝
| A | B | (A v B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
- Բարդ բանաձևի օրինակ
p q ~ (~ p & ~ q) (p v q) 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 1 3 1 0 2 1 0
- տրամաբանական հետևություն
A B (A -> B) 0 0 1 0 1 1 1 0 0 1 1 1 (A->B) համարժեք է ~(A & ~B)
- տրամաբանական նույնություն
A B (A = B) 0 0 1 0 1 0 1 0 0 1 1 1 (A=b) համարժեք է (A->B)&(B->A)
- Տավտալոգիա (tautology)
Ա ասույթային բանաձևը կանվանենք տավտոլոգիա, եթե միշտ ընդունում է 1 արժեքը
- Օրինակ.
- (p V ~p),
- (pVq)=~(~p&~q) (p&q)=~(~pV~q) (de Morgan’s lows)
- ((p->q)&~q)->~p (Modus tollens)
- (p->q)=(~q->~p) ()
- Օրինակ.
- Հակասություն (Contradiction)
ասույթային բանաձևը կանվանենք տավտոլոգիա, եթե միշտ ընդունում է 0 արժեքը
- Օրինակ.
- (p & ~p),
- (p->q)&(p->~q)
- Օրինակ.
- Կատարելի (satisfiable) ունի առնվազմն մեկ հատ 1 իր ճշմարտության աղյուսակում
- Դիպվածային (contingent) Եթե Կատարելի է բայգ տավտոլոգիա չէ
- ասույթային բանաձևը տավտոլոգիա է
- միայն ու միայն այն դեպում եթե ~A is not satisfiable
- միայն ու միայն այն դեպում եթե ~A is a contradiction
- Տրամաբանական հետևություն (consequence)
կասենք Բ բանաձևը Ա բանաձևի տրամաբանական հետևություն է, եթե
այն տողերում որտեղ Ա բանաձը ճիշտ է Բ էլ է ճիշտ:
A |= B
A logical implies B - ենթադրել
A logical entails B - հանգեցնել
Օրինակ. p & ~q |= ~p V ~q, քանի որ
p q p & ~q ~p V ~q 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 - Տրամաբանական նույնություն (equivalence)
կասենք Ա բանաձևը տրամաբանորեն նույնական է Բ բանաձևին,
եթե բոլոր տողերում Ա և Բ բանաձևերը ընդունում են նույն արժեքները:
A
|B Թերորեմ: կամայական A և B ասույթային բանաձևեր հարաբերվում են որպես.- տրամաբանական նույնություններ A
|B- միայն ու միայն այն դեպքում, երբ A|= B և B |= A:
- միայն ու միայն այն դեպքում, երբ (A = B) տավտալոգիա է
- տրամաբանական հետևություն A |= B միայն ու միայն այն դեպքում, երբ (A -> B) տավտալոգիա է
- տրամաբանական նույնություններ A
- Տրամաբանական հակասություն (contradictories)
կասենք Ա բանաձևը տրամաբանորեն հակասական է Բ բանաձևին,
եթե բոլոր տողերում Ա և Բ բանաձևերը ընդունում են հակադիր արժեքներ:
A
|B Թերորեմ: կամայական A և B ասույթային բանաձևեր տրամաբանական հակասական են, եթտ- միայն ու միայն այն դեպքում, երբ A
|~B - միայն ու միայն այն դեպքում, երբ (A = ~B) տավտալոգիա է
- միայն ու միայն այն դեպքում, երբ A
- Տրադիցիոն տրամաբանանակն հարաբերություններ
- հակասություն contraries
Ա և Բ բանաձևերը հակասական են, եթե նրանք երկուսն էլ չեն կարող լինել ճշմարիտ՝
Բ սխալ է այն տողերում երբ Ա ճիշտ է, և Ա սխալ է երբ Բ ճիշտ է:
~(pvq) p&q, these formulas are contraries but does not sub-contraries.
Թերորեմ: կամայական A և B ասույթային բանաձևեր հակասություններ են, եթե
- միայն ու միայն այն դեպքում, երբ A |= ~B
- միայն ու միայն այն դեպքում, երբ (A -> ~B) տավտալոգիա է
- ենթահակասություն sub-contraries
Ա և Բ բանաձևերը ենթա-հակասական են, եթե նրանք երկուսն էլ չեն կարող լինել սխալ՝
Բ ճիշտ է այն տողերում երբ Ա սխալ է, և Ա ճիշտ է երբ Բ սխալ է:
Թերորեմ: կամայական A և B ասույթային բանաձևեր ենթա- հակասություններ են, եթե
- միայն ու միայն այն դեպքում, երբ ~A |= B
- միայն ու միայն այն դեպքում, երբ (~A -> B) տավտալոգիա է
- հակասություն contraries
Ա և Բ բանաձևերը հակասական են, եթե նրանք երկուսն էլ չեն կարող լինել ճշմարիտ՝
Բ սխալ է այն տողերում երբ Ա ճիշտ է, և Ա սխալ է երբ Բ ճիշտ է:
~(pvq) p&q, these formulas are contraries but does not sub-contraries.
Թերորեմ: կամայական A և B ասույթային բանաձևեր հակասություններ են, եթե
- պնդումը կապում է նախադրյալները(premises) եզրահանգմանը: Կան լավ և ոչ այնքան լավ պնդումներ: Տրամաբաններին հետաքրքրում է ինչով է պայմանավորված տարբերությունը:
- պնդումը վավերական է եթե բոլոր նախադրյալները ճիշտ են ապա եզրահանգումը նույնպես ճիշտ է: Պնդում որոնք պարունկաում է A1, A2, …, An նախադրյլանե և B եզրահանգումը մենք կգրենք A1, A2, …, An |= B, պնդումը որ A1, A2, …, An հետևում է B վավերական է: arguemnt from premisies to conclusion B is valid.
- օրինակ.
A1 = (p&~q)->r
A2 = ~r
B = p->q
պետք է ստուգենք A1, A2 |= B պնդման վավերականությունը
# p q r (p&~q)->r ~r p -> q 1 0 0 0 1 1 1 + 2 0 0 1 1 0 1 3 0 1 0 1 1 1 + 4 0 1 1 1 0 1 5 1 0 0 0 1 0 6 1 0 1 1 0 0 7 1 1 0 1 1 1 + 8 1 1 1 1 0 1 վավերականություն հաստատելու համար պետք է նաենք այն տողերը որտեղ A1 և A2 նախադրյալները ընդունում են ճշմարիտ արժեք. 1-ին, 3-րդ և 7-րդ տողերը և համոզվենք որ համապատասխան տողերում եզրահանգումը նույնպես ընդունում է ճշմարիտ արժեք, հետևաբար վավերական է մեր պնդումը:
տրամաբանական հետևության և տավտոլոգիայի հարաբերությունից կարող են տալ համապատասխան հարաբերություն պնդման վավերականության և տավտոլոգիայի միջև: Թեորեմ. պնդումը A1, A2, …, An նախադրյալներից դեպի եզրահանգումը վավերական է, այսինքն A1, A2, …, An |= B , միայն ու միայն այն դեպքում (iff) (A1 & A2 & … & An) -> B տավտոլոգիա է, այսինքն (A1 & A2 & … & An) |= B Σ A |= B iff Σ |= A->B
Խոսակցական լեզվով արտահայտված պնդումը կարելի է ներկայացնել տրամաբանական ձևերով որպես տրամաբանական պնդում և ստուգել վավերականուլյունը, այդ ներկայացում միարժեք չէ: պնդումը դա բանաձևերի ցուցակ է՝ մեկ և ավել նախադրյլաների և մեկ եզրահանգման:- Soundness of Argument An argument is sound if and only if it is an instance of a valid argument form, and in addition, the premises are in fact all true.
- Sound arguments are instances of valid argument forms whose promises are also true.
- But, some instances of invalid argument forms can still be valid arguments.
- For an argument to be invalid, there has to be at least one situation in which the premises are all true, but the conclusion is false at the same time.
- A & B = True, mean
A B
- ~(A & B) = True, mean / \ ~A ~B
- (A v B) = True, mean / \ A B
- ~(A v B) = True, mean A = B = False, since we write ~A, ~B in proof tree we write only True forms of atoms
~A ~B
- A -> B = True, mean / \ ~A B
- ~(A -> B)
A ~B
- A = B / \ A ~A B ~B
- ~(A = B) / \ A ~A ~B B
- ~~A
A
- A closure rule ~A x close this branch
- George Bool (1815-1864) founder of propositional logic and boolean algebra
- Charles Sander Peirce (1839-1914) Truth tables, not-or/or connectives(Peirce arrow) Pragmatic theory of language of truth. first use Boolean algebra and propositional logic to analyse relay and switching circuits.
- Claude Elwood Shannon (1916-2001) Information theory, define what is mean digitize analog signal and deconstruct it to analog.
- Years 1937: first binary adder 1947: first poin-contact transistor 1958: first integrated circuit 1969: birth of ARPANET, precursor of internet 1991: first digital mobile phones
memristor can implement both
- comninational digital system
- sequential digital system
- Combinational digital systems: memoryless
The current value of each output signal is a function of the current value of the input signals
-and does not depend on past value of input signals.
Examples of usage or key classes of job done by combinational digital systems:
- Encoding and decoding
- Selecting and distibuting multiplexers (MUX) is data selector and demultiplexers(DEMUX) is data distributor
- Binary arithmetic
- Comparison and classifications
- Sequential digital systems: contain memporu via combinational and delat components in feedback loops, plus digital clock. Memory registers are used to keep track of past values of input signals, with values in memory recorded by internal state signals, together with clock imput signal to keep time. in second oart of this course will learn about this kind of systems.
All classic propositional connectives can be expressed in terms fo NAND (or NOR) ~A ≡ (A|A) (AvB) ≡ ((A|A)|(B|B)) (A&B) ≡ ((A|B)|(A|B))
Basic Constructors:
- AND, OR, NOT gates
- NAND only
- NOR only
- Functional descriptions
- Truth tables
- Logic formulas
- Logic Circuit diagrams
How to transfor one representation to another.
Functional Description - pushing the button on cell phone system has: 10 inputs: p0,p1,p2,p3,p4,p5,p6,p7,p8,p9 4 data outputs: m3, m2, m1, m0 1 error signal: r such that: if exactly one on the inputs pi is active then r = 0 and q is 4bit value of decimal i, while if either zero or more of the imputs are active, then r is 1 and m=0000.
Truth Table rows = 2 * 10, only 10 row is matter, when r=0, others do not care -no matter
| p0 | p1 | p2 | p3 | p4 | p5 | p6 | p7 | p8 | p9 | r | m3 | m2 | m1 | m0 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| s1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| s2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | |
| s3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | |
| s4 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
Introduce intermediate signals for 10-input AND gates: s0 ≡ (p0 & ~p1 & ~p2 & ~p3 & ~p4 & ~p5 & ~p6 ~p7 & ~p8 & ~p9) s1 ≡ (~p0 & p1 & ~p2 & ~p3 & ~p4 & ~p5 & ~p6 ~p7 & ~p8 & ~p9) .............. From truth tables to logical formula, we see m3 ≡ (s8 v s9) m2 ≡ (s4 v s5 v s6 v s7), ≡ read if only if m1 ≡ (s2 v s3 v s6 v s7) m0 ≡ (s1 v s3 v s5 v s7 v s9) r ≡ ~(s1 v s2 v s3 v s4 v s5 v s6 v s7 v s8 v s9)
Method:from truth table to logic formula From a truth table column for output z depending on inputs p1,p2, up to pn, (in truth table with 2 ^ n rows)
- Look down column for output z and identify each of the rows in which output is 1.
- For each such row, write down the size-n conjunction of inputs or negated inputs which uniquely describes that row: if input pi is 0 on that row, include ~pi in conjunction; if input pi is 1 on that row, include pi in conjunction.
- Output z is equivalent to the disjunction of all these row-conjunctions; if there are m-many rows in which output z is 1, then it will be a size-m disjunction.
Disjunctive Normal Form A logic formula A is in disjunctive normal form (DNF) iff A is a disjunction of conjunctions of literals, where a literal is either an atomic proposition or the negation of an atomic proposition. Called sum-of-products (SOP) form in digital systems and Boolean algebra literature.
DNF circutir can be easily transfered to NAND only gates circuit.
Functional description: take as input two data input signals x and y, together with a select input signal s, and produce as output data signal z such that z ≡ x if s is 0 and z ≡ y if s is 1. input data: x, y imput signal: s output: z 3-inout, 1-output system
Truth table
| row | x | y | s | z | s = 0 | s = 1 | row conjuction/minterm(product term) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | z ≡ x | ||
| 1 | 0 | 0 | 1 | 0 | z ≡ y | ||
| 2 | 0 | 1 | 0 | 0 | z ≡ x | ||
| 3 | 0 | 1 | 1 | 1 | z ≡ y | (~x&y&s) | |
| 4 | 1 | 0 | 0 | 1 | z ≡ x | (x&~y&~s) | |
| 5 | 1 | 0 | 1 | 0 | z ≡ y | ||
| 6 | 1 | 1 | 0 | 1 | z ≡ x | (x&y&~s) | |
| 7 | 1 | 1 | 1 | 1 | z ≡ y | (x&y&s) |
Logical formula characterise the output signal ‘z’, expressed using bi-conditional. z ≡ ((~x&y&s) v (x&~y&~s) v (x&y&~s) v (x&y&s)) this is DNF formula in the boolean algebra and digital system literature, minterms or product term, because logical onjuction is the boolean product operation.
Is that DNF is smallest??
Karnaugh map method is a systematic method for deriving a minimal DNF from the truth table for a propositional logic formula or combinational system.- If a statement is contradictory in classical two-valued logic, then it is super-false in every supervaluation model.
- All classical two-valued tautologies are super-true in all supervaluation models.
- The fuzzy logic analysis of the sorties paradox takes the sorties argument to be invalid, but with all premises true to a high degree.
- f a statement is super-false in a supervaluation model M, it will remain super-false in a model found by deleting one or more valuations from M.
- In the supervaluationist analysis of the sorties paradox, in a typical sorties argument, no premise is super-false, but they aren’t all super-true.
- The epistemicist analysis of the sorties paradox takes the sorties argument to be valid but not sound.
Examples of vagueness color gradient strip big and small
An vagueness is just one of the issues thet help us examine the assumptions we’ve made in the two-valued picture of logic.
▶Color gradint examplein details Red -> Yellow 1-10000 patches ri: patch i looks red. r1 seems true. r10000 seems false. ri => ri+1 (if ri then ri+1) is true r1, r1=>r2, r2=>r3,…r9900=>r10000 |- r10000 is valid and this is the problem
- all primises seems true
- the argument seems valid
- the conclusion seems false
these 3 things can’t all be as they seem, since a valid argument with two primises doesn’t have a false conclusion, its conclusion’s got to be true. And this is the Sorites paradox.
▶ Four options to respond the Sorites paradox.
- Logic does not apply to vague expressions.
- Logic does apply, and the argument is not valid.
- Logic does apply, the argument is valid but one of the premises is false.
- Logic does apply, the argument is valid and sound, and therefore the conclusion is true.
- Logic does apply, and the argument is not valid.
Jan Łukasiewicz: Famous for Many-Valued Logics ▶ A ⊃ B If i(A) <= i(B) then i(A⊃B) = 1 If i(A) > i(B) then i(A⊃B) = 1 - i(A) + i(B) ▶ A & B = min(i(A), i(B)) ▶ A v B = max(i(A), i(B)) ▶ ~A = 1 - i(A)
i(∼A)=1−i(A). i(A⊃B)=1 if i(B)≥i(A), and i(A⊃B)=1−i(A)+i(B) if i(A)>i(B). i(A&B) is the smaller value of i(A) and i(B). i(A∨B) is the larger value of i(A) and i(B).
▶ When is argument valid? An argument from Σ to B t-valid iff whenever i(A) >= t for each A in Σ then i(B) >= t too. (Think of t as the threshold to count as true.) ▶ if the argument from Σ to A is t-valid we we’ll write ‘Σ |=t A’ ▶ An argument is absolutely valid iff it is t-valid for every t.
▶two value logic to approach vagueness- Logic does apply, the argument is valid but one of the premises is false.
▶ Supervaluations super-true super-false gap
▶Epistemicism
▶Are there formulas composed out of p, q or r which we can choose for A and B to show that (A&(A⊃B))⊃B does not get the value 1? i(p)=1, i(q)=2/3, i(r)=1/4Yes, for example: i((q&(q⊃r))⊃r)=4/12
▶If A⊃B isn’t super true, then B isn’t super-true either.? Yes
implicative - կզորդչական, իմաստարկու Implicature - the phenomenon by which we can say one thing by way of saying another different thing. Implication - Կցորդություն, մասնակցություն, խառնում, ակնարկություն, լռելեայն իմաստ, իմաստարկություն▶linguistics: the study of language in all its aspects.
- Phonetics and phonology
- Morphology
- Syntax
- Semantics
- Pragmatics
- Discourse analysis
- …
- Computer Software
- used in semantics of programming languages
- analysis of programs
- automated reasoning intelligance
- Computer Hardware - analysis and design digital circuits grounded in logic:
- combinational circuits = classical propositional logic
- sequential circuits = propositional temproal logic or predicate logic.
Pre-history of Automated Reasoning
- Thomas Hobbes (1588-1679) Human reasong or ratiocination
- Gottfried Wilhelm Leibniz (1646-1716) characteritica universalis - a universal symbolic langugage for science, math and philosophy.
- David Hilbert (1862-1943) Hilbert’s mathematical program(1920): attempting to show that all of mathematics follows from a correctly chosen finite system of axioms; and that some such axioms system can be shown to be provably consistent.
- Kurt Godel(1906-1978) Godel’s invompleteness theorems (1931): any formal logic system expressive enough to describe arithmetic on the natural numbers (1) is incomplete if it is consistent; and (2) the consistency of the system cannot be proved within the system itself.
- Alan Turing (1912-954) Turing formalised concepts of computation and algorithm with Logical Computing Machine model, subsequently called Turing machine model. Turing 1936: the Halting Problem for Turing machines is algorithmically undecidable: it is not possible to decide algorithmically whether a given Turing machine will halt on a given input.
Computing logical consequence to programm computer to think logically the core job to compute consequence given logical formulas A1, A2,…, An and B determine wheather or not: A1, A2,…, An |= B Direct semantic evaluation in Propositional Logic: k-many atomic propositions in A1, A2,…, An and B gives 2 ^ k-many truth table rows/valuations, so an explicit check of all of these is dumb and impractical.
Practical Automated Reasoning To find decidable, and practically computable, classes of logical consequence problem: ▶ restrict to a simple fragment of the language: program clauses and goals (together known as Horn clauses); ▶ use a proof system with only one rule: keep it simple for dumb machines!
Logic Programming is a direct, declarative style of computer programming using logic-based languages such as prolog or datalog.
- Practical Automated Reasoning
To find decidable, and practically computable, classes of logical consequence problem: ▶restrict to a simple fragment of the language: program clauses and goals;
- A program clause or definite clause is a formula of one of two kinds:
- conditional rule - (p1 & p2 & … & pn) => q, where n>=0, and p1, p2, …, pn, q all atomic formulas.(case n=0 gives facts.)
- fact - q
- Logic program A logic program P is a list A1, A2,…,An of program clauses.
- Goals A goal G is s list r1,r2,..,rk of atmos, and the corresponding goal formula is the conjuction B = (r1 & r2 & … & rk)
- Automated reasoning task: determine wheather or not: P |= G that is, A1, A2,…, An |= B
▶use a proof system with only one rule: a resolution rule; keep it simple for dumb machines! Logic Programming is a direct, declarative style of computer programming using logic-based languages such as prolog or datalog.
4x4 toy Sudoku puzzles| A | B | C | D |
| E | F | G | H |
| I | J | K | L |
| M | N | O | P |
A correctly completed 4x4 Sudoku must contain a permutation of {1;2;3;4} in the cells of each row, each column, and each block
for make sure that each puzzle has uniq solutions we init some cells with numbers
| A | B (1) | C | D |
| E | F | G (2) | H |
| I | J | K | L (4) |
| M (3) | N | O | P |
▶ Resolution rule G=q,r1,r2,…,rk, k>=0 PROOLOG will look for a program clause A in P whose head is q. if A is conditional rule or proper program clause, with >= 1; q :- p1,p2,…,pm. then the new goal G’ replaces the q in G with body atoms p1,p2,…,pn, and G’ is the resolvent og G with clause A.
G = q,r1,r2,…,rk, k>=0
| A |
| / |
G’= p1,p2,…,pm,r1,r2,…,rk
Each program clause q :- p1,p2,…,pm. (m>=0) is logically equivalent to the disjunction: q v ~p1 v ~p2 v … v ~pm
goal just a list of atoms. For each goal r1,r2,…,rk. (k>=1) Goal formula is the conjuction of this atoms ri. B = r1&r2&…&rk then the ~B = ~r1 v ~r2 v … v ~rk
▶ Literal - an atmoic formula or the negation of an atomic formula , and a clause is a disjunction of literals. Clause - is a disjunction of literals
▶Clausal Form In Clausal Form: (1). program clauses include exactly one positive literal (the head q), and the rest are negative literals. Written in clausal form: {q, ~p1, ~p2, …, ~pm} (2). negated goal formulas include zero positive literals, as all its literals are negative. Written in clausal form {~r1,~r2, …, ~rk}
▶Horn Clause A logic formula is a Horn clause if and only if it is logically equivalent to a clause with at most one positive clause. These combines program clauses and negated goal cluases into one class. Resolution method were first developed for the Horn clause fragment of logic, and then specialised in the implementation of PROLOG.
▶Refutation(հերքում) approach puts together a logic program with the negated goal, and tries to derive a contradiction.
▶negation simbol \+▶for treatment of negation in PROLOG, extinctions use a concept called the close world assumption, or alternatively going to what’s called non monotonic logic’s.
A program clause or definite clause is written in prolog as: q :- p_1, p_2,…, p_m. or q. where m >= 0 and p_1, p_2,…,p_m, q are all atomic formulas. (Case m = 0 gives facts.) Read “:-” as “if”, and commas between p_i’s as “and” “:-” - reverse conditional
▶ Meaning of program clauses (m>=1): We can establish the atom q if we first establish all of p_1,p_2, and up to p_m. ▶Facts q. have no body, just a head. ▶Atoms must have names starting with a lower-case letter, then followed by upper-case letters, lower-case letters, digits or an underscore _. ▶Program clauses must end with “.” . ▶The order of atoms within a clause, and the order of program clauses in a program, both matter in how prolog runs.
Logic: Language and Information 2 - first order predicate logic
⊃, ∨, ∧, ¬, ≡, ≠, ∀, ∃, λ, ≤, ≥, ∈, ∉, ∞, ▶ • ‘ ’
▶ All wombats are quadrupeds. Will is a wombat. Therefore, Will is a quadruped. ▶Invalid in propositional logic due to word “Some” Somw wombats are quadrupeds. Will is a wombat. Therefore, Will is a quadruped.
▶ All wombats are quadrupeds. Will is a wombat. Therefore, Will is a quadruped. To expose this structure, we’ve got to use new CATEGORIES. • Name - Will. • Predicate - wombat, quadruped. • Quantifier - All We will construct formulas out of names, predicates and quantifiers. ▶Names things - a name used to pick out an entity for our consideration • Aristotle the philosopher who first construct a system of logic for analysing statement like we had about “wombat” above. • Ada Lovelace - wrote worlds first program run on Charles Babbage’s difference machine. • Will • Melburne • Five - number • Pegasus - flying horse in methology ▶Predicates - describes things or categorising In forumlas, we use upper case letters like ‘F’, ‘G’ for predicates. Predicates describe or relate things.• … is a quadruped. (has one space to field by a name) • … is a multiple of ten. (has one space to field by a name, when we supply a name, we get a sentence.) • … is taller than … (we called two place predicate, has room for two names, when we supply two names, we get a sentence. this related things, pairs the things) • … is a multiple of … - two place predicate • … loves … - two palce predicate • … is between … and … - three place predicate ▶Predicates and Arity Predicate with name(s) makes an atomic proposition. • ‘ … is a quadruped ’ one place predicate called - unary, monadic • ‘ … loves … ’ requires exactly two - the lover and the beloved.
The number of names predicate needs is called its arity. ▶ Predicates, Names and Propositions Now we can form simple propositions.
| Sentence | Form |
|---|---|
| Will is a quadruped | Qw |
| Clancy loves Medison | Lcm |
| Clancy and Medison love each other | Lcm & Lmc |
| Clancy and Medison love themselves | Lcc & Lmm |
| Clancy’s love for Modison is unrequited | Lcm & ~Lmc |
▶ ∀∃ vs ∃∀ • (∀x)(∃x)Lxy - Everyone loves someone. Choice for y dependes on each choice for x. • (∃x)(∀x)Lxy - There is a someone loved by everyone. One choice for y for all choices for x.
▶ Example 1 - Some Victorian Englishwoman wrote a computer program. • Create a Dictionary Vx = x is Victorian. Ex = x is English. Wx = x is a woman. Px = x is a computer program. Rxy = x wrote y.
(∃x)((Vx & (Ex & Wx)) & (∃y)(Rxy & Py))
▶ Example 2 - Every Victorian Englishwoman wrote a computer program. Vx = x is Victorian. Ex = x is English. Wx = x is a woman. Px = x is a computer program. Rxy = x wrote y.
(∀x)((Vx & (Ex & Wx)) & (∃y)(Rxy & Py)) - This means “Everything is a Victorian Englishwoman who wrote a computer program.” (∀x)((Vx & (Ex & Wx)) ⊃ (∃y)(Rxy & Py))
▶ Example 3 - Every philosopher knows a linguist who owns a dog. Px = x is a philosopher. Lx = x is linguist. Dx = x is a dog. Kxy = x knows y. Oxy = x owns y.
(∀x)(Px ⊃ (∃y)(Ly & Kxy & (∃z)(Dz & Oyz))) ▶ Example 4 - Every student has read some book on our reading list. Sx = x is a student. Bx = x is a book. l = our reading list. Rxy = x has read y. Oxy = x is on y.
(∀x)(Sx ⊃ (∃y)((By & Oyl) & Rxy))
In the nex classes, we will take a look at how to interpret this language. We’ll look at what we need to see wheather a sentcence in this language is true or false. And what it means for logical concepts, like
- equivalence
- consistency
- logical consequence
to apply to sentences in the language of first order predicate logic.
The basic task in interpreting a language is to provide the means to determine which sentences or formulas are true and which are false.A model is some fragment of the world we want to talk about. ▶Interpretation of Propositional logic • For proposition logic this was quite easy. Each valuation specifies the truth or falsity of atomic which describes one row of a truth table. For propositional logic we can simply specify which of the atomic sentences are true and which ones are false. • Truth tables for the connectives do the rest. • For predicate logic we need to do more ▶Semantics and the Interpretation of predicate logic - Interpreting Fa • A model has to give every formula a truth value. Instead of valuations ans rows of a truth table, predicate logic uses models, and each model must contain the ingredient to give every formula a truth value.
▶ How will we interpret Fa? • Start with an atomic formula Fa where ‘a’ is a name and ‘F’ is a 1-place predicate. • What is the interpretation of name a? - An object The interpretation of name ‘a’ is an object named by that name. • So, the interpretation of a 1-place predicate, F will need to addign a truth value to every pbject. • (Similarly, to interpret a 2-place predicate, we assign a truth value to every pair of objects, etc.)
▶ Sudoku 4x4 game Example different fragmetn of the world In this part of the world, the objects of interest are the 16 cells in the grid which we’ve name a,b,c,d,…,n,o,p As well as the number values of assigned to those cells.
• We can express the basic fact set such as cell g has value 2 with an atomic formula like “Vg2”. • We can epxress that cell “f” and cell “g” are in the same row, or row related, with an atmoic formula “Rfg” • We can express more complex fact, that applies to all cells, and all number values in the puzzle, ‘for all “x” and for all “y”, and for all “z”, if “x” has value “y”, and “x” is row related to “z” then it is not the case that “z” has value “y” ‘. (∀x)(∀y)(∀z)((Vxy & Rxz) ⊃ ~ Vzy) this formula will be true in 9x9 Sudoku puzzles as well as out little fours ones.
| formulas | |||||
|---|---|---|---|---|---|
| a | b 1 | c | d | ||
| e | f | g 2 | h | Vg2 | |
| i | j | k | l 4 | Rfg | |
| m 3 | n | o | p |
▶Talking about Numbers Let capital ‘E’ be a 1-place predicate meaning is an even number. E2, ~E3 - are both truth in this model Let capital ‘O’ be a 1-place predicate meaning is an odd number. ~O2, O3 - are both truth in this model This model of the natural numbers makes true the quantified formula for all x, either Ex or Ox. (∀x)(Ex ∨ Ox) - Since all natural numbers are either even or odd. (∀x) ~(Ex & Ox) - Since no number can be both even and odd.
While it is easy to see that the previous two quantifier formulas are true in this model of the natural numbers, it is not hard to devise formulas whose truth or falsify is unknown or yet to be determined.
▶ Goldpack conjecture One of the most famous unsolved probems in mathematics is the Goldbach conjecture in number theory, which assets that every even number greater than two can be expressed as ths sum of two prime numbers. (∀x)((Ex & Gx2) ⊃ (∃y)(∃z)(Py & Pz & Sxyz)) - for all even numbers greater than two, there exists a y and z such that y and z are both prime and x is the result of adding y and z. e.g. 12 = 5 + 7 64 = 17 + 47 Where, ‘G’ is two place redicate with Gxy meaning ‘s is greater thatn y’. ‘P’ is one place predicate meaining, ‘is a prime number’. ‘S’ is three place predicate meaning ‘x is the sum of y and z’.
Goldpach conecture empirically verified up to at least 4 e 18 (4 quintillion) … but there is not proof that it is tru for all natural numbers. So it is still unknown whether the universally quantified formula here is true or false of the natural numbers.
▶The Domain of a Model A model has a non-empty colelction of objects, D, its domain. • Each model of the predicate logic must have non empty collection of objects called its domain. • Each name in the language is interpreted by an object in domain. That is clear, names name objects. • Each predicate is interpreted by a domain a truth value for each object (or pair, triple, …) from the domain. Each 1-place predicate is interpreted by a truth value of each object in the domain. Each 2-place predicate is interpreted by a truth value for each ordered pair of objects in the domain. And so on • The quantifiers for all and there exists range over objects in the domain.
▶ Summary A model of predicate logic consists of two parts • a domain • an interpretation where the interpretation must interprets names as object int the domain. And also interpret, predicate by distribution of truth values over objects int the domain.
A model for predicate logic is analogous to one row of a truth table in propositional logic. In each case, they contain all the information required, to determine the truth value of atomic formulas of the language. Predicate and proposition respectivelly.
A model consists of • A domain - a non-empty collection of objects. • An interpretation for every name - i.e. an object. • An interpretation of every predicate - i.e. a distribution of truth values over the domain.
Next In the next lession we will formally define models and give more examples.
Keep in mind, that a model for predicate logic is analogous to one row of a truth table in propositional logic. In each case, they contain all the information required, to determine the truth value, of atomic formulas ot the languages. ▶ Model • A non-empty DOMAIN D of objects. • An INTERPRETATION FUNCTION I(.), which interprets each name and predicate in the language.We will write a model M as a pair (D,I) to indicate these two parts.
▶ Example • Model contains 3 objects, three scentiest
- Ada Lovelace: the 19th century English mathematician
- Kurt Godel: the Austrian Czech logician
- Albert Einstein: German born physicist
• Now, suppose our language includes two names, ‘a’ and ‘b’. And they have to be met to some objects in the domain. n ^ m We could interpret ‘a’ = Godel, and ‘b’ ad Einstein. Or have ‘a’ nad ‘b’ denote to Godel Or both denoting Lovelace, and so on. • The only requirement on an interpretation I, is that each name in the language, must be mapped to an object in the domain.
• If ‘a’ is a name, then I of ‘a’ - I(a) is an object in the domain.
• In our model we have 3 objects {Ada, Godel, Einstein} How many different ways are there to assign objects to ‘a’ and ‘b’?
Now let’s turn to interpreting predicates • Let ‘F’ is 1-place predicate, if we interpret ‘F’ to mean he is a mathematician then ‘I of F’ will assign one or true to Lovelace and Godel and zero or false to the Einstein to to physicist Einstein.
▶ Interpreting Predicates In our domain D={l,g,e}, suppose the 1-place predicate F in interpreted to mean “is a physicist”. An interpretation I for F divides the domain in two.
| I(F) | |
|---|---|
| I | 0 |
| g | 0 |
| e | 1 |
This 1-dminsional table describes the interpretation I(F) of the predicate symbol F.
2 ^ n
▶2014 World leaders model D={Obama,Xi,Merkle,Abe} From model to truth • atmoic formulas Fa we need the interretation of name ‘a’ we need the interpretation of predicate simbol ‘F’ suppose a=Xi F I(F) Rab - a is older than bM=(D,I) D={Obama,Xi,Merkle,Abe} I(a)=Xi, I(b)=Merkel
| I(F) | I(G) | |
|---|---|---|
| Obama | 1 | 1 |
| Xi | 1 | 0 |
| Merkel | 0 | 0 |
| Abe | 0 | 1 |
| I(R) | Obama | Xi | Merkel | Abe |
|---|---|---|---|---|
| Obama | 0 | 0 | 0 | 0 |
| Xi | 1 | 0 | 1 | 1 |
| Merkel | 1 | 0 | 0 | 1 |
| Abe | 1 | 0 | 0 | 0 |
▶ ▶ ▶
▶ In a model with a finite domain, we can simplify the clauses for truth in a model for quantified formulas. • In a finite model M, formula (∀x)A is true in M iff the conjuction of all its instances is true in the model M. • In a finite model M, formula (∃x)A is true in M iff the disjunction of all its instances is true in model M.• Example if D={o,i,m,e} is the domain of model M then (∀x)Rax is true in the model M iff Rao & Rai & Ram & Rae is trye in M
This means that if we focus on a particular finite model, the quantifiers are useful, and let us be more concise, but they do not give us anything we cannot say with ‘&’ and ‘V’. But this change when we go infinite models.
▶ Infinite model We need our original definition of truth in a model because some models are infinite.
• Consider arithmetic, with domain D={0,1,2,3,…} • Look at the 2-place predicate S, interpreted as “is triclty smaller than”
Let’s evaluate some formula in this mdoel
| I(S) | 0 | 1 | 2 | 3 | 4 | … |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | … |
| 1 | 0 | 0 | 1 | 1 | 1 | … |
| 2 | 0 | 0 | 0 | 1 | 1 | … |
| 3 | 0 | 0 | 0 | 0 | 1 | … |
| 4 | 0 | 0 | 0 | 0 | 0 | … |
| . | . | . | . | . | . | . |
| . | . | . | . | . | . | . |
| . | . | . | . | . | . | . |
• (∀x)S0x is true iff all the instances are true, S00, S01, S02, … are all true But S00 is false So (∀x)S0x evaluate to false.
• (∀x)(∃y)Sxy is true iff all the isntances are true (∃y)S0y, (∃y)S1y, (∃y)S2y … are all true Sxy mean x < y
▶ Using model to calssify▶ … what the world needs to be like for them to be true ▶ Classifications • TAUTOLOGY - A formula A is a TAUTOLOGY iff is true in every model M. • CONTRADICTION - Ex. (∃y)(∀x)Rxy & ~(∀y)(∃x)Rxy • Contingent - A formula ‘A’ is contingent iff it is true in at least one mode, and false in another model. In other words, ‘A’ is contingent iff is not a contradiction and it is not a tautology, etiher.
▶ Realtionsheeps • Logical consequence A |= B Formula ‘B’ is Logical consequence of formula ‘A’ exactly when for every model in which ‘A’ is true, ‘B’ is true too. We write this as A |= B. Notice: A |= B iff (A ⊃ B) is a tautlogoy.• Logical Equivalence A | B
Formula ‘A’ and ‘B’ are Logical equivalence iff for every model ‘A’ and ‘B’ have the same truth value.
Notice:
A | B iff (A ≡ B) is a tautology.
• Contradictories
Formula ‘A’ and ‘B’ are contradictories iff for every model ‘A’ and ‘B’ have oposite truth value.
Notice:
A | B iff (A ≡ ~B) is a tautology.
▶ Validity for arguments X |= A Let X be a set of formulas, and let A be a single formula. An argument from premises X to conclusion A is valid iff in every model M in which each formula in X is true, A is also true in M.
•
▶ Rules for quantifier formulas • Exsitential (partial rule) (∃x)AA[x:=n] ‘n’ new
• Negated Existential (general rule) ~(∃x)A
~A[x:=a] any ‘a’
• Universal (general rule) (∀x)A
A[x:=a] any ‘a’
• Negated Universal (artial rule) ~(∀x)A
~A[x:=n] ‘n’ new
•
▶ Ex 1. Is this tautology? |- (∀x)(Fx ⊃ (∃y)(Fy)) ~(∀x)(Fx ⊃ (∃y)(Fy)) a~(Fa ⊃ (∃y)(Fy))
Fa ~(∃y)(Fy) \ a
~Fa x closed it is tautology
▶ Ex 2. (∀x)(Fx ∨ Gx) |/- (∀x)Fx ∨ (∀x)Gx
(∀x)(Fx ∨ Gx) \a, b (3) (7 branch for b) ~((∀x)Fx ∨ (∀x)Gx) (1)
~((∀x)Fx a (2) ~((∀x)Gx b (5)
~Fa
Fa ∨ Ga (4) / \ Fa Ga x | ~Gb (6)
Fb ∨ Gb (8) / \ Fb Gb x
we will use open branch to cosntruct a Domain D={a,b}
| I(F) | I(G) | |
|---|---|---|
| a | 0 | 1 |
| b | 1 | 0 |
▶ Ex 3. (∃x)(Fx ∨ Gx) |- (∃x)Fx ∨ (∃x)Gx (∃x)(Fx ∨ Gx) a (3) ~((∃x)Fx ∨ (∃x)Gx) (1)
~(∃x)Fx \a (2) (5) ~(∃x)Gx \a (2) (7)
Fa ∨ Ga (4) (9)
~Fa (6)
~Ga (8) / \ Fa Ga (10) x x
How to extend predicate logic syntax,semantix and proof tree to handle the notion of Identity and difference. ▶ Identity is a binary predicate. we use infix form • a = b, we do not write “= a b” like regular binary redicate • a ≠ b ▶ • ▶ •