Hoorcollege 1 Logic
sections:
1.1 (declarative sentences)
1.3 (propositional logic as a formal language)
1.4.1 (the meaning of logical connectives) 6 februari 2018
Declarative sentences
● A declarative sentence (or proposition) is a statement that is true or false.
● Argument abstraction
○ Example:
■ If the train arrives late, and there are no taxis at the station, then Jane
is late for her meeting.
■ Jane is not late for her meeting.
■ The train does arrive late.
■ Therefore, there are taxis at the station.
■ If it is raining, and John did not take his umbrella with him, then he will
get wet.
■ John is not getting wet.
■ It is raining.
■ Therefore, John did take his umbrella with him.
○ Key of translation
■ p the train arrives late
■ q there are taxis at the station
■ r Jane is late for her meeting
■ p it is raining
■ q John takes his umbrella with him
■ r John is getting wet.
○ Abstraction:
■ If p and not q, then r.
■ Not r. p. Therefore, q.
○ Formalization:
■ (((p ^ -q) → r) ^ (-r ^ p)) → q
○ Validity:
■ Validity of the two arguments due to the logical form.
■ It does not depend on the actual content of p, q and r.
● Symbols of propositional logic
○ Propositional variables (which can be true or false):
■ p, q, r, …
○ Connectives:
■ ^ ‘and’ (conjunction)
■ v ‘or’ (disjunction)
■ ⊕ ‘either … or … ‘ (‘exclusive or’)
■ ⇁ ‘not’ (negation)
, ■ → ‘if … then … ‘ (implication)
■ ↔ ‘ if and only if’ (bi - implication)
■ Not in the scope of propositional logic are constructs like:
● for all, there exists (will be treated in lecture 6)
● must, may, always, eventually, I know that
● Sentences and formulas:
○ propositional structure of sentences
■ 5>3 p
■ grass is green p
■ grass is green and roses are blue p^q
■ if x > 1, then x^2 ≠ x p →⇁ q
● What are the p and q in the last example?
○ ⇁p where p represents “I wear glasses”
○ q where q represents “I don’t wear glasses”
● Formulas of propositional logic
○ Building blocks:
■ p, q, r, … are propositional variables
■ ⇁ is a unary connective (takes one argument)
■ ^, v, ⊕, →, ↔, are binary connectives (takes multiple arguments)
○ The construction of formulas:
■ Inductive definition:
● (BASE STEP) every propositional variable is a formula
● (CONSTRUCTION STEPS)
1. if Φ is a formula, then so is (⇁ Φ)
2. if Φ and ψ are formulas, then so are (Φ ^ ψ), (Φ v ψ),
(Φ ⊕ ψ), (Φ → ψ) and ( Φ ↔ ψ)
● Parsing a formula
○ A formula can be reconstructed from its parse tree:
○
, ○
● Omitting parentheses
○ To omit parentheses from formulas, without causing ambiguity, we use the
priority schema:
■
■ Question: Which parentheses can be omitted from?
● None
● Truth value semantics for propositional logic
○ Formulas of propositional logic are used to express declarative statements,
which are either true or false.
○ We introduce the truth values Τ and F, corresponding to truth and falsehood,
respectively.
○ The truth value of a composite formula (like Φ ^ ψ) is determined by the truth
values of its components Φ and ψ.
○ For each connective this functional behavior is expressed by its truth table.
● Negation
○ A negation ⇁ Φ (“not Φ”) is
{ true if Φ is false
{ false if Φ is true
● Conjunction
○ A conjunction Φ ^ ψ (“Φ and ψ”) is
{ true if Φ is true and ψ is true
{ false in all other cases
, ● Disjunction
○ A disjunction Φ ^ ψ (“Φ or ψ”) is
{ true if Φ is true, or ψ is true, or both;
{ false otherwise
● Inclusive versus exclusive or
○ Examples in natural language:
■ Inclusive:
● Do you take sugar or cream in your coffee?
■ Exclusive:
● Do you want a cappuccino or an espresso?
○ Exclusive or
■ An exclusive or Φ ⊕ ψ (“either Φ or ψ”) is
{ true if either Φ or ψ is true (but not both)
{ false otherwise
● Implication
sections:
1.1 (declarative sentences)
1.3 (propositional logic as a formal language)
1.4.1 (the meaning of logical connectives) 6 februari 2018
Declarative sentences
● A declarative sentence (or proposition) is a statement that is true or false.
● Argument abstraction
○ Example:
■ If the train arrives late, and there are no taxis at the station, then Jane
is late for her meeting.
■ Jane is not late for her meeting.
■ The train does arrive late.
■ Therefore, there are taxis at the station.
■ If it is raining, and John did not take his umbrella with him, then he will
get wet.
■ John is not getting wet.
■ It is raining.
■ Therefore, John did take his umbrella with him.
○ Key of translation
■ p the train arrives late
■ q there are taxis at the station
■ r Jane is late for her meeting
■ p it is raining
■ q John takes his umbrella with him
■ r John is getting wet.
○ Abstraction:
■ If p and not q, then r.
■ Not r. p. Therefore, q.
○ Formalization:
■ (((p ^ -q) → r) ^ (-r ^ p)) → q
○ Validity:
■ Validity of the two arguments due to the logical form.
■ It does not depend on the actual content of p, q and r.
● Symbols of propositional logic
○ Propositional variables (which can be true or false):
■ p, q, r, …
○ Connectives:
■ ^ ‘and’ (conjunction)
■ v ‘or’ (disjunction)
■ ⊕ ‘either … or … ‘ (‘exclusive or’)
■ ⇁ ‘not’ (negation)
, ■ → ‘if … then … ‘ (implication)
■ ↔ ‘ if and only if’ (bi - implication)
■ Not in the scope of propositional logic are constructs like:
● for all, there exists (will be treated in lecture 6)
● must, may, always, eventually, I know that
● Sentences and formulas:
○ propositional structure of sentences
■ 5>3 p
■ grass is green p
■ grass is green and roses are blue p^q
■ if x > 1, then x^2 ≠ x p →⇁ q
● What are the p and q in the last example?
○ ⇁p where p represents “I wear glasses”
○ q where q represents “I don’t wear glasses”
● Formulas of propositional logic
○ Building blocks:
■ p, q, r, … are propositional variables
■ ⇁ is a unary connective (takes one argument)
■ ^, v, ⊕, →, ↔, are binary connectives (takes multiple arguments)
○ The construction of formulas:
■ Inductive definition:
● (BASE STEP) every propositional variable is a formula
● (CONSTRUCTION STEPS)
1. if Φ is a formula, then so is (⇁ Φ)
2. if Φ and ψ are formulas, then so are (Φ ^ ψ), (Φ v ψ),
(Φ ⊕ ψ), (Φ → ψ) and ( Φ ↔ ψ)
● Parsing a formula
○ A formula can be reconstructed from its parse tree:
○
, ○
● Omitting parentheses
○ To omit parentheses from formulas, without causing ambiguity, we use the
priority schema:
■
■ Question: Which parentheses can be omitted from?
● None
● Truth value semantics for propositional logic
○ Formulas of propositional logic are used to express declarative statements,
which are either true or false.
○ We introduce the truth values Τ and F, corresponding to truth and falsehood,
respectively.
○ The truth value of a composite formula (like Φ ^ ψ) is determined by the truth
values of its components Φ and ψ.
○ For each connective this functional behavior is expressed by its truth table.
● Negation
○ A negation ⇁ Φ (“not Φ”) is
{ true if Φ is false
{ false if Φ is true
● Conjunction
○ A conjunction Φ ^ ψ (“Φ and ψ”) is
{ true if Φ is true and ψ is true
{ false in all other cases
, ● Disjunction
○ A disjunction Φ ^ ψ (“Φ or ψ”) is
{ true if Φ is true, or ψ is true, or both;
{ false otherwise
● Inclusive versus exclusive or
○ Examples in natural language:
■ Inclusive:
● Do you take sugar or cream in your coffee?
■ Exclusive:
● Do you want a cappuccino or an espresso?
○ Exclusive or
■ An exclusive or Φ ⊕ ψ (“either Φ or ψ”) is
{ true if either Φ or ψ is true (but not both)
{ false otherwise
● Implication
