CHAPTER 7 - Propositional Logic

Propositional Logic

is the simplest form of logic where all the statements are made by propositions.

Proposition

is a declarative statement which is either true or false. It is a technique of knowledge representation in logical and mathematical form

Logical constants, propositional logic, wrapping parenthesis

propositional logic consists of what 3 parts? (LPW)

Conjunction

^ (and)

Disjunction

v (or)

implication/conditional

-> (implies)

Biconditional

Negation

' (not)

Literal

atomic sentence or negated atomic sentence

Semantics

A simple language useful for showing key ideas and definitions. User defines a set of propositional symbols, like P and Q

sentence

a (well formed formula), and is defined as follows:

• A symbol is a sentence

• If S is a sentence, then S' is a sentence

• If S is a sentence, then (S) is a sentence

• If S and T are sentences, then (SvT), (S^T), (S→T), and (S

• A sentence results from a finite number of applications of the above rules

Semantics

The meaning or _________ of a sentence determines its interpretation.

Evaluated

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

model for a KB

is a "possible world" (assignment of truth values to propositional symbols) in which each sentence in the KB is True.

Tautology

A valid sentence or _________ is 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."

contradiction

An inconsistent sentence or _____________ is a sentence that is False under all interpretations. The world is never like what it describes, as in "It's raining and it's not raining."

P entails Q

means that whenever P is True, so is Q. In other words, all models of P are also models of Q

Commutativity Law

P∧Q = Q∧P, or

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

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

¬(¬P) = P

All, some, none

We cannot represent relations like ___, ____, or ____ with propositional logic. Propositional logic has limited expressive power. In propositional logic, we cannot describe statements in terms of their properties or logical relationships.