Propositional logic

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
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 A q : F
p A -q: T p v q : T
p © q: T
p ^ q: F
q ^ p: 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.
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

Translation
Assume a sentence:
If you are older than 13 or you are with your parents then you can attend a PG-13 movie.
Parse:
• If ( you are older than 13 or you are with your parents ) then (you can attend a PG-13 movie)
Atomic (elementary) propositions:
- A= you are older than 13
- B= you are with your parents
- C=you can attend a PG-13 movie
• Translation: A v B ^ C