المحاضرة الاولى هياكل متقطعة

Propositional logic: review
• Propositional logic: a formal language for representing
knowledge and for making logical inferences
• A proposition is a statement that is either true or false.
• A compound proposition can be created from other
propositions using logical connectives
• The truth of a compound proposition is defined by truth
values of elementary propositions and the meaning of
connectives.
• The truth table for a compound proposition: table with
entries (rows) for all possible combinations of truth values of
elementary propositions.
CS 441 Discrete mathematics for CS M. Hauskrecht
Compound propositions
• Let p: 2 is a prime ….. T
q: 6 is a prime ….. F
• Determine the truth value of the following statements:
¬ p: F
p ? q : F
p ? ¬q: T
Computer representation of True and False
We need to encode two values True and False:
• Computers represents data and programs using 0s and 1s
• Logical truth values – True and False
• A bit is sufficient to represent two possible values:
– 0 (False) or 1(True)
• A variable that takes on values 0 or 1 is called a Boolean
variable.
• Definition:A bit string is a sequence of zero or more bits.
The length of this string is the number of bits in the string.
p ? q : T
p ? q: T
p ? q: F
q ? p: T
3
CS 441 Discrete mathematics for CS M. Hauskrecht
Constructing the truth table
• Example: Construct the truth table for
Applications of propositional logic
• Translation of English sentences
• Inference and reasoning:
– new true propositions are inferred from existing ones
– Used in Artificial Intelligence:
• Rule based (expert) systems
• Automatic theorem provers
• Design of logic circuit