Chapter 7_Propositional Logic

Propositional Logic

• The simplest form of logic where all statements are made by propositions;

• a technique of knowledge representation in logical and mathematical form.

Proposition

A declarative statement which is either true or false.

Logical Constants

True, False.

Propositional Symbols

P, Q, S, ... (atomic sentences).

Wrapping parentheses

( … )

Literal

Atomic sentence or negated atomic sentence.

Negation (¬)

• "…not";

• a sentence such as ¬P

• is called the _____ of P.

Conjunction (∧)

• "…and";

• a sentence which has the connective ∧,

• such as P ∧ Q.

Disjunction (∨)

• "…or";

• a sentence which has the connective ∨,

• such as P ∨ Q,

• where P and Q are the propositions.

Implication (⇒)

• "…implies";

• a sentence such as P → Q.

• Also known as an if-then rule or conditional.

Biconditional (⇔)

• "…is equivalent";

• a sentence such as P ⇔ Q.

Semantics

• A simple language useful for showing key ideas and definitions.

• The user defines a set of propositional symbols, like P and Q.

• The user defines the meaning of each propositional symbol.

Sentence (Well Formed Formula)

• A symbol is a _____.

• If S is a sentence, then ¬S and (S) are _____.

• If S and T are _____, then (S ∨ T), (S ∧ T), (S → T), and (S ⇔ T) are _____.

• Results from a finite number of applications of the above rules.

Interpretation

• The meaning or semantics of a sentence.

• Given the truth values of all symbols in a sentence, it can be "evaluated" to determine its truth value (True or False).

Model

• A "possible world" (assignment of truth values to propositional symbols)

• in which each sentence in the KB is True.

Valid Sentence (Tautology)

• A sentence that is True under all interpretations,

• no matter what the world is actually like or how the semantics are defined.

• Example: "It's raining or it's not raining."

Inconsistent Sentence (Contradiction)

• A sentence that is False under all interpretations;

• the world is never like what it describes.

• Example: "It's raining and it's not raining."

Entailment (P |= Q)

• P entails Q means that whenever P is True, so is Q;

• all models of P are also models of Q.

Parenthesis,

Negation,

Conjunction (AND),

Disjunction (OR),

Implication,

Biconditional

Precedence of Connectives, from first to sixth (6)

Commutativity Law

• P ∧ Q = Q ∧ P;

• P ∨ Q = Q ∨ P.

Associativity Law

• (P ∧ Q) ∧ R = P ∧ (Q ∧ R);

• (P ∨ Q) ∨ R = P ∨ (Q ∨ R).

Identity Element

• P ∧ True = P;

• P ∨ True = True.

Distributive Law

• P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R);

• P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).

De Morgan's Law

• ¬(P ∧ Q) = (¬P) ∨ (¬Q);

• ¬(P ∨ Q) = (¬P) ∧ (¬Q).

Double-negation Law

¬(¬P) = P.

Cannot Represent ALL, Some, or None

• Propositional logic cannot represent relations like _____, _____, or _____.

• Examples: "All the girls are intelligent."

• "Some apples are sweet."

Limited Expressive Power

Propositional logic has _____.

No Properties or Relationships

In propositional logic, statements cannot be described in terms of their properties or logical relationships.