Chapter 5 : Logic and Boolean Algebra Flashcards
What is the basis of all mathematical reasoning, and of all automated reasoning
- Logic
What makes up a correct mathematical argument?
- Proof
What is called when we prove a mathematical statement is true?
- Theorem
What is used to verify that computer programs produce the correct output for all possible input values?
- Proofs
What is a proposition?
- Declarative sentence
- Means a sentence that declares a fact ( Which return True or False )
What is a Notation?
- Variables are used to represnt propositions
List out 4 conventional letters used for propositional variables ( Notation )
- p
- q
- r
- s
List out 2 values for truth value of proposition
- True - T
- False - F
Determine which is / isn’t a propositional logic and list out the truth values of those that are propositions
1. “Listen”
2. “What time is it?”
3. “x + 2 = 2 and x + y = z”
4. 2 is a prime number
5. Kuala Lumpur is the capital of Malaysia
- Not a proposition
- Not a proposition
- Not a proposition
- Question doesn’t provide values for x , y and z
- A proposition , True
- A proposition , True
Determine which is / isn’t a propositional logic and list out the truth values of those that are propositions
1. 2 + 3 = 5
2. 5 + 7 = 10
3. x + 2 = 11
4. 2 + 3 = 4
5. Read this carefully
6. Cat is an insect
7. Answer this question
8. What time is it?
- A proposition , True
- A proposition , False (5 + 7 not equal to 10 )
- Not a proposition
- Question doesn’t provide values for x
- A proposition , False (2 + 3 not equal to 4 )
- Not a proposition
- A proposition , False ( Cat isn’t an insect )
- Not a proposition
- Not a proposition
What are compound compositions?
- Mathematical statements are constructed by combining one or more propositions
- Formed from existing propositions using logical operators
How are compound compositions formes?
- From existing propositions using logical operators
What does logical operations include?
- Comparisons of 2 data
- Result will be either True or False
How can logical operations be represented ?
- Using truth table ( True - 1 , False - 0 )
What determined the number of rows inside a truth table?
- All the possible values taken by the propositions involved in the statement
- If a compound statement containes n proposition variables there will need to be 2^n rows in the truth table
List out all 6 nouns for Logical Connectives
- Negation
- Conjunction
- Disjunction
- Exclusive Disjunction ( XOR )
- Implication / Conditional
- Biconditional
What is the connectives and symbol for negation?
- Connectives
- not
- Symbol
- ~
- ¬
- Think of it as a Not Gate
What is the connectives and symbol for conjunction?
- Connectives
- and
- but
- Symbol
- （ ^ ）
What is the connectives and symbol for disjunction?
- Connectives
- or
- Symbol
- ∨
What is the connectives and symbol for implication / conditional?
- Connectives
- if .. (p) .. then only .. (q) ..
- Symbol
- p → q
What is the connectives and symbol for exclusive disjunction?
- Connectives
- exclusive or ( xor )
- Symbol
- ⊕
What is the connectives and symbol for negation?
- Connectives
- if ..(p).. and only if ..(q)..
- Symbol
- p ↔ q
List out the truth table of Negation
p ¬p
T F
F T
- Not Gate
- It is the statement “It is not the case that p”
- Opposite truth value of p
Find the negation of the following and then express in simple english
1. Today is Friday
2. At least 10 inches of rain fell today in Miami
3. 1 + 1 = 2
4. Lions cannot fly
5. I will study hard, or I will not pass this course
6. 1 + 2 = 3 or 2 + 1 = 3
- Today is not Friday
- Less than 10 inches of rain fell today in Miami
- At Least ( > 10 ) , Negation Less than ( 10 < )
- 1 + 1 ≠ 2
- Lions can fly
- I will not study hard, and I will pass this course
- = ~ ( 1 + 2 = 3 ) and ~ ( 2 + 1 = 3 )
= 1 + 2 ≠ 3 and 2 + 1 ≠ 3
What are 2 keywords that is being used inside conjunction?
- But ( Sometimes used instead of and )
- And
What is the condition of conjunction?
- p and q ( p ^ q ) when both p and q are true
Construct the truth table of conjunction
p q p ^ q
T T T
T F F
F T F
F F F
What are the keywords in disjunction?
- or
What is the condition of disjunction?
- p or q ( p ∨ q ) is false when both p and q are false
Construct a truth table for disjunction
p q p ∨ q
T T T
T F T
F T T
F F F
What is the keywords for exclusice disjunction?
- exclusive or
- p or q but not both
What is the condition for exclusive disjunction?
- p exclusive or q ( p ⊕ q ) is true when exactly one of p and q is true and it is false otherwise
- True when 1 is true and another one is false
Construct a truth table for exclusive disjunction
p q p⊕q
T T F
T F T
F T T
F F F
- The room has 2 light switches controlling one light bulb. If both switches are on, the light if off. IF one is ON, the light is on, if none is ON, the lights is off
- Think of it like telling a child they can have candy, or ice cream. But they can’t have both!
What is the keyword for expression implication ( conditional ) ? ( 8 )
Condition follow Conclusion
1. if p, then q
2. p implies q
3. p is sufficient for q
4. p only if q
** Conclusion follow by Condition**
5. q when p
6. q whenever p
7. q, if p
8. q is necessary for p
What is the condition for implication?
- p implies q ( p → q ) is false when p is true, and q is false and it is true otherwise
- It is only false when p is true but q is false
Construct truth table for implication
p q p→q
T T T
T F F
F T T
F F F
List out 3 ways to represent the conditional statements in English
p : Maria learns discrete mathematics
q : Maria will find a good job
p→q
- If Maria learns discrete mathematics, then she will find a good job
- Maria will find a good job when she learns discrete mathematics
- For Maria to get a good job, it is sufficient for her to learn discrete mathematics
What is the keyword for expressing biconditional?
- p if only if q
- p iff q
- If p then q, and conversely
- p is necessary and sufficient for q
What is the condition for biconditional?
- p if and only if q ( p ↔ q ) is true when p and q have the same truth values
When both value for p → q and q → p is true, p ↔ q will be returning true
Construct a truth table for biconditional
p q p → q q → p p ↔ q
T T T T T
T F F T F
F T T F F
F F T T T
Determine whether each of these conditional and biconditional statements are true?
1. If 1 + 1 = 2 , then 2 + 2 = 5
2. 0 > 1 if and only 2 > 1
3. 2 - 7 = -5 if and only if -7 < -5
4. 169 is a perfect square
5. The product of a^4 and a^3 is a^12
- False
- False
- True
- True 13^2 = 169
- a^4 . a^3 = a^ ( 4 + 3 ) = a^7
How can the following English sentence can be translated into a logical expression?
“You can access the internet from the campus only if you are a computer science major or you are not a freshmen”
p : You can access the internet from the campus
q : You are a computer science major
r : You are a freshmen
Ans : ( p → q ) ∨ ~r
How can the following English sentence can be translated into a logical expression?
“You cannot ride a roller coaster if and only if and only if you are under 4 feet tall and you are not older than 16 years old”
p : You can ride a roller coaster
q : You are under 4 feet tall
r : You are older than 16 years old
~p ↔ q ^ ~r
Transform logical expressions to English sentences
p : Alice is smart
q : Alice is honest
1. ~p ^ q
2. p ∨ ( ~p ^ q )
3. p → ~q
- Alice is not smart but honest
- Either Alice is smart or she is not smart but honest
- If Alice is smart, then she is not honest
Given
p : The file system is full
q : The automated reply can be sent
Express the specification “ The automated reply cannot be sent when the file system is full “ using logical connectives
- ~q → p
List out the precedence ( priority ) of operators in symbols ( Top to bottom )
- ~
- ^ ( And )
- ∨ ( Or )
- → ( Conditional )
- ↔ ( Biconditional )
What does logical equivalent ( ≡ ) represents ?
- 2 statements ( Left & Right ) have the same Truth Table in all possible cases
List out 3 logical equivalence statement
- Tautology
- Truth value in all possible cases is True
- Contradiction
- Truth value in all possible cases is False
- Contigency / Indeterminant
- Truth value in all possible cases is Some True and False
Prove that p ∨ q ≡ ~ ( ~p ^ ~q )
p q p∨q ~p ~q ~p ^ ~q ~ ( ~p ^ ~q )
F F F T T T F
T F T F T F T
F T T T F F T
T T T F F F T
Construct a truth table and state whether it is tautology, contradiction or contingency
1. ( A ∨ B ) ^ ( ~A )
A B A ∨ B ~A ( A ∨ B ) ^ ( ~A )
F F F T F
T F T F F
F T T T T
F F F T F
Ans : Contingency
What does computer used to represent information?
- bits
What is the possible value for bits?
- 0
- 1
- Since bit is called binary digit
What is the rule of precedence of Boolean Algebra?
- Parentheses / Brackets
- Complement ( NOT )
- Product ( AND )
- Sum ( OR )
Show that ( 1’ . 0’ ) + ( 1 . 0’ ) = 1
( 1’ . 0’ ) + ( 1 . 0’ )
= ( 0 . 1 ) + ( 1 . 1 )
= 0 + 1
= 1
What is NOT gate also known as?
- Inverter
List out the truth table for NOT gate
A A’
0 1
1 0
_
A
List out what symbols used in the gate below:
1. AND Gate
2. OR Gate
- A x B ( A . B )
- A + B
List out the truth table for AND gate
A B A.B
0 0 0
0 1 0
1 0 0
1 1 1
List out the truth table for OR Gate
A B A+B
0 0 0
0 1 1
1 0 1
1 1 1
List out the truth table for NAND Gate
A B A.B (A.B)’
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
List out truth table for NOR Gate
A B A+B (A+B)’
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
List out truth table for XOR Gate
A B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0
- If 2 value are the same ( 1 , 1 ) , ( 0 , 0 ), it will be 0
- If A and B are the same value , the gate isn’t happy - Abubakar
Which Boolean Identities is important during exam?
- Distributive Laws
- x + yz = ( x + y )( x + z )
- x ( y + z ) = xy + xz
- De Morgans’ Laws
- (xy)’ = x’ + y’
- ( x + y ) ‘ = x’y’
- Absorption Laws
- x + ( xy ) = x
- x ( x + y ) = x
- Redundancy Laws ( Deal with complement )
- x + x’y = x + y
- x ( x’ + y ) = xy
Prove that A + A . B = A
A + A . B ( Absorption Law )
= A
A + A . B
= A . 1 + A . B Identity Law
= A ( 1 + B ) Distributive Law
= A . 1 Dominance Law
= A Identity Law
Until Slide 56 ( Don’t need to include Questions in Boolean Identities , Just proceed with questions now )
Write out truth table for p q r
p q r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
1st Column
T
T
T
T
F
F
F
F
2nd Column
T
T
F
F
T
T
F
F
3rd Column
T
F
T
F
T
F
T
F
List out truth table for p q
p q
T T
T F
F T
F F
1st Column
T
T
F
F
2nd Column
T
F
T
F
