Transcript IM_FA16-01b-Sentence

385T Information Modeling — Class 01b
Unit 1: First Order Logic
Sentence Logic:
Syntax and Semantics
Slides for August 24
Karen Wickett, [email protected]
School of Information
University of Texas at Austin
Fall 2016
1
Unit 1: First Order Logic
• Class 01a: Basic Concepts
• Class 01b: Sentence Logic: Syntax and Semantics
• Class 02: Sentence Logic: Inference (ND and TT)
• Class 03: Predicate Logic: Syntax and Semantics
• Class 04: Predicate Logic: Inference (Truth Trees)
• Class 05: Metatheory
2
Sentence Logic (SL) — Syntax and Semantics
• SL is a formal language that can model (some) information …
and support the derivation of inferences from modeled
information.
• All information modeling systems are based on SL.
• Although not always explicitly
• And not always all of SL
• And not always only SL
3
Overview of main topics: Sentence Logic
• SL Syntax
(Teller: “Formation Rules”)
• A formal specification of the vocabulary items in SL and how those items can be
combined. More specifically a syntax says what is, and isn’t, a sentence of SL.
• SL Semantics
(Teller: “Evaluation Rules”)
• Initially: A formal definition of what it means for sentences in SL to be true
• Ultimately: … and what it is for sentences in SL to be consistent, inconsistent
(contradictory), logically true (tautologous), and logically equivalent; what it is
for one sentence to be a logical consequence of another; and what it is for
arguments to be valid.
• Translation from natural languages into SL
(Teller: “Transcription”)
• Using SL to model the world typically means re-expressing assertions expressed
in a natural language (such as English) in the language of SL.
• SL Inferencing
•
•
•
•
(Methods for determining truth-functional validity)
Method 1: Truth tables: Algorithmic, but inefficient.
Method 2: Natural Deduction: Efficient, but non-algorithmic,
Method 3: Truth trees: Efficient and algorithmic for SL. (aka semantic tableaux).
[other methods include resolution (based on normal forms) and axiomatic proof]
• SL Metatheory
• Generalizations about the nature of SL modeling and inferencing methods.
4
 Truth Functional Deductive Validity
Recall our general provisional definition of [deductive] validity.
• It is impossible for (the premises to be true and the conclusion false)
i.e …
—In every possible situation where the premises are true
the conclusion is true also.
—There is no possible case, no counterexample, in which the premises
are true and the conclusion false.
—In every possible world in which the premises are true, the conclusion
is true.
At the heart of SL is the identification of a particular kind of [deductive]validity:
truth functional deductive validity
5
A selection from our examples of valid arguments
1) If John is home then Jill is home;
2) John is home
3) Therefore Jill is home
1) If John is home then Jill is home;
2) Jill is not home
3) Therefore John is not home
1) John is home or Jill is home;
2) John is not home
3) Therefore Jill is home
1) John is home and Jill is home
2)Therefore John is home
1) If John is home then Jill is home;
2) If Jill is home then Jane is home;
3) John is home
4) Therefore Jane is home
6
Our examples, schematically…
1) If P then Q;
2) P
3) Q
1) If P then Q;
2) not-Q
3) not-P
1) P or Q;
2) not-P
3) Q
1) P and Q
2) P
1) If P then Q;
2) If Q then R;
3) P
4) R
7
The fundamental intuitions behind truth-functional
propositional logic
• In at least some intuitively valid arguments (like those on the previous slide), the
conclusion follows from the premises solely in virtue of the meaning of the bolded
words
• We call these words sentence connectives.
• More specifically, there is no way for the premises to be true and the conclusion
false that is consistent with the intuitive meaning of these connectives.
• … no possible “assignment of truth values to the conclusions and premises”
that is consistent with the meaning of the sentence connectives
and that would make the premises true and the conclusion false.
• And that seems to be because the connectives are being used to make assertions
about the truth or falsity of the sentences they connect.
• In fact the “meaning” of these connectives seems simply to consist in what they
tell us about the truth of their component sentences.
8
The meaning of the connectives
• “It is not the case that A”
• means A is false
[~A]
• “A and B”
[A & B]
• means both A and B are true
• “A or B”
[A v B]
• means at least one of A and B are true
• “If A then B”
[A  B]
• mean either A is false or B is true
• “A if and only if B”
[A  B]
• means A and B have the same truth value
9
 The Big Picture on Sentence Logic
• Sentence Logic (SL) is a language for representing arguments as sequences of
sentences, either atomic (e.g. “A”) or (truth-functional) compounds (e.g. “A v B”),
and testing for validity.
• SL can determine whether the argument is valid in virtue of the truth-functional
meaning of its sentence connectives.
• We define SL (as we define any logical language) by providing (i) a syntax and (ii)
a semantics…
• [Teller: “formation rules” and “evaluation rules”]
• We then develop inferencing techniques: procedures for determining whether or
not a conclusion follows from a set of premises. [Class 02]
• We then step back and explore analyze various characteristics of the system we have
built (metatheory). [Class 05]
• We evaluate SL’s adequacy as a general information modeling system; here we
will be especially concerned with the expressiveness of the language and the
efficiency of its proof procedures.
10
 Syntax of SL
Vocabulary
•
A, B, C, …
these are atomic sentences
•
&, V, , , ~
•
these are sentence connectives, the first four dyadic (binary), the last monadic
Grammar
[In what follows we use "X" and "Y" as metalinguistic variables that stand in for,
or “range over”, sentences (atomic or compound) in the language SL]
1) A, B, C, … are sentences of SL
2) If X is a (atomic or compound) sentence of SL, then so is (~X), “… the sentence
formed by taking X, writing a “~” in front of it, and surrounding the whole by
parentheses “(Teller).
3) If X and Y are sentences of SL, then so is (X & Y), “that is …“
4) If X and Y are sentences of SL, then so is (X v Y), “… ”
5) If X and Y are sentences of SL, then so is (X  Y), “that is…”
6) If X and Y are sentences of SL, then so is (X  Y)
7) Nothing else is a sentence of SL
11
Terminology and Conventions
•
Terminology
•
Individual sentence letters are atomic sentences
•
Compounds formed with connectives are compound sentences
•
The X’s and Y’s in each case of compounding are called the immediate constituents of
the compound in which they occur.
•
A & B … is a conjunction, (A AND B), its immediate constituents, are its conjuncts.
•
A v B … is a disjunction; (A OR B) , its immediate constituents, are its disjuncts.
•
Note: A is not an immediate constituent of (A v B) & C
•
A  B … Is a conditional or implication;
A is its antecedent and B is its consequent.
•
~A … a negation
•
A  B … is a (material) biconditional; A and B are its terms.
12
Syntax conventions
Parentheses style may be alternated for clarity: “()”, “[]”, “{}”.
Parentheses are omitted when no ambiguity results.
•
Outermost parentheses are dropped
•
Where X is an atomic sentence we write ~X, not ~(X);
—we adopt the rule that "~" applies to the shortest string possible:
—i.e. "~AvB" means "(~A)vB" not "~(AvB)".
13
Recursive Syntax Definitions
•
The definition of “sentence in SL” is recursive.
•
It defines membership in a class in terms of operations on class
members, specifying a base set of members to get things started.
•
Another account:
— A recursive definition (or inductive definition) in mathematical logic and computer
science is used to define an object in terms of itself.
(http://en.wikipedia.org/wiki/Recursive_definition)
•
•
In the case of SL, this takes the form of specifying a base set of objects
(the vocabulary) and then defining the entire language in terms of ways
to combine those objects (the grammar).
Such definitions are extremely important to the development of formal
information modeling systems — not just SL, but almost all modeling
languages.
14
Significance of Recursive Definitions
•
Why are they so important? Several reasons…
1)
Using only a finite vocabulary of symbols a recursive definition defines
a language with a infinite number of sentences.
2)
A recursive definition provides a mechanical decision procedure (an
algorithm) for determining whether a given string of symbols is a
sentence in the language.
3)
A recursive definition for the syntax of SL supports a truth functional
semantics for SL, as we will see.
4)
Whenever a language is defined recursively it is possible to use
mathematical induction to prove fundamental facts about it.
— Mathematical induction is not a proof technique that is used in logic, but
one used to prove things about logic. It is therefore important not for
information modeling per se, but for the science of information modeling.
More in this in Class 05.
•
BTW this is also our first informal and brief glimpse of a “formal grammar”. Not only are
formal grammars used to define modeling languages (cf. Chapter 6 of Elmasri and Navathe).
But as used in HTML, TEI, etc. it is a modeling strategy in its own right. Unit 4 is devoted to
formal grammars.
15
Applying the Definition (Parse Tree)
main connective
((A v B) & Q)

(R  ~S)
(R  ~S)
((A v B) & Q)
(A v B)
A
Q
B
immediate components
R
~S
S
Using the definition of sentence-in-SL to determine whether or not a string of
symbols, here, “((A v B) & Q)  (R  ~S)”, is a sentence in SL
16
Scope and "()”. Syntactic vs Semantic Differences
•
Note the parentheses required by the syntax definition (formation rules).
•
In use parentheses distinguish "((AvB)vC))" from "(Av(BvC))"
•
These are syntactically different sentences: compare their parse trees, or their
immediate constitutents.
•
Conventions to reduce the number of parentheses are sometimes used (slide 13).
•
Sometimes "operator scope" makes a semantic as well as syntactic a difference:
•
”(9+3)+2” has a different parse tree than ”9+(3+2)”, but they both evaluate to the
same number, 15. However ”(9+1)2" and ”9+(12)” evaluate to different
numbers are well as having different parse trees.
•
Now consider the pairs
i. “(A & B) & C” and “A & (B & C)”
ii. “(A & B) v C” and “A & (B v C)”
The first pair have different parse trees, but are logically equivalent.
The second pair have different parse trees and are not logically equivalent.
Rules of "operator precedence" could be adopted to further reduce the number of
parenthesis. However we do not use them, nor does Teller. They are risky, obviously.
17
Semantics of SL (informally)
 Syntax tells you what a correctly formed sentence is;
 Semantics tells you under what conditions a correctly formed sentence is true.
The semantics for SL has two components, one for atomic sentences and one for
compound sentences.
 Atomic sentences: In any possible situation each atomic sentence has exactly one
of two “truth values”, True ("T") or False ("F”).
 … not both,
 … and not neither
 … exactly one.
 But which it is, T or F, is not for the logician to say, for that you need to get up out
of your chair and look around at the world.
 Compound sentences: In every possible situation a compound sentence is assigned
a value (T or F, but not both) that is determined by the values (in that situation) of
its “immediate constituents”, in the following way…
18
 Valuation Rules for SL (Semantics)
•
Negation: ~X is true if and only if X is false
•
Conjunction: X & Y is true if and only if both X is true and Y is true,
•
Disjunction: X v Y is true if and only if either (or both) X is true or Y is true
•
Conditional: X  Y is true if and only if either (or both) X is false or Y is true
•
Biconditional: X  Y is true if and only if X and Y have the same truth value
•
In SL if a sentence is not true it is false.
*Compare this with Teller. Like the formation rules, this way of giving the semantics
is more compact then Teller’s evaluation rules, and very common in information
modeling.
19
 Truth Tables
• Truth tables come in two kinds
• those with simple sentences in the column headings in the
guide column headings and compound sentences in the other
column headings.
—these are used to evaluate the truth value of compound SL sentences
and the validity of SL arguments
—they let us display all possible assignments of truth values to atomic
sentences and examine the results.
•
those with sentence variables in the column headings, and
sentence forms for compound sentences in the rest.
—these are used to display the truth-functional meanings of connectives
and learn how to evaluate the truth value of SL compounds
• More in-depth discussion of truth tables next week.
20
Defining Semantics of SL Connectives
Using a Sentence-Variable -based truth table
X
Y
~X
XvY
X&Y
XY
XY
T
T
F
T
T
T
T
T
F
F
T
F
F
F
F
T
T
T
F
T
F
F
F
T
F
F
T
T
Where the italicized letters X and Y are “metalinguistic” variables
ranging over sentences (either simple or compound) of SL.
This table is a visual summary of slide 19.
21
Truth-Functional Validity
• Provisional account of validity in general: it is impossible for the premises to
be true and the conclusion false.
• Initial intuition for truth-functional validity: The meanings of the various
sentence connectives will not allow an assignment of Truth to the premises
and False to the conclusion.
• Mature definition of truth-functional validity: There is no assignment of truth
values to simple sentences that, given the truth-functional definitions of
sentence connectives (as given in their truth tables) will make the premises
true and the conclusion false.
• A counterexample (or sometimes “countermodel”) is an assignment of truth
values to the simple sentences that makes the premises true and the
conclusion false.
• Identifying a counterexample proves that an argument is not valid
• Proving that there cannot be a counterexample proves that an argument is
valid.
22
Truth Table Determination of Validity
• Consider these arguments…
AB
A
B
A&B
A
AvB
~A
B
We can determine that there is no counterexample by examining
every possible distribution of truth values,
by building a truth table that represents the truth values of the
premises and conclusion for every possible case and inspecting it
to see whether there is any case where the premises are true and
the conclusion false.
23
Truth Table Evaluation of Validity: Modus Ponens
Argument: A  B, A, B
Simple
Premise 1
Premise 2
Conclusion
Sentences
Row
A
B
AB
A
B
1
T
T
T
T
T
2
T
F
F
T
F
3
F
T
T
F
T
4
F
F
T
F
F
No.
Q: Is this a valid argument?
24
Truth Table Evaluation of Validity: Modus Ponens
Argument: A  B, A, B
Simple
Premise 1
Premise 2
Conclusion
AB
A
B
Sentences
Row
A
B
1
T
T
2
T
F
3
F
T
4
F
F
No.
Q: Is this a valid argument?
25
Truth Table Evaluation of Validity: Modus Ponens
Argument: A  B, A, B
Simple
Premise 1
Premise 2
Conclusion
Sentences
Row
A
B
AB
A
B
1
T
T
T
T
T
2
T
F
F
T
F
3
F
T
T
F
T
4
F
F
T
F
F
No.
A: Only one assignment, Row 1, makes both the premises true, and that assignment also
makes the conclusion true.
So there are no assignments that make the premises true and the conclusion false -- and so
the argument is valid.
26
Truth Table Evaluation of Validity:
for “The fallacy of affirming the consequent”
Argument: A  B, B, A
Simple
Premise 1
Premise 2
Conclusion
AB
B
A
Sentences
Row
A
B
1
T
T
2
T
F
3
F
T
4
F
F
No.
Q: Is this a valid argument?
27
Truth Table Evaluation of Validity:
for “The fallacy of affirming the consequent”
Argument: A  B, B, A
Simple
Premise 1
Premise 2
Conclusion
Sentences
Row
A
B
AB
B
A
1
T
T
T
T
T
2
T
F
F
F
T
3
F
T
T
T
F
4
F
F
T
F
F
No.
A: Two assignments make the premises true, and while one of those assignments
makes the conclusion true as well, the other makes the conclusion false (row 3).
So there is an assignment that makes the premises true and the conclusion false -- and
so the argument is invalid.
28