Chapter 5 : Logic and Boolean Algebra

Question 1

What is the basis of all mathematical reasoning, and of all automated reasoning

Answer 1

1. Logic

Question 2

What makes up a correct mathematical argument?

Answer 2

1. Proof

Question 3

What is called when we prove a mathematical statement is true?

Answer 3

1. Theorem

Question 4

What is used to verify that computer programs produce the correct output for all possible input values?

Answer 4

1. Proofs

Question 5

What is a proposition?

Answer 5

1. Declarative sentence
   
   • Means a sentence that declares a fact ( Which return True or False )

Question 6

What is a Notation?

Answer 6

1. Variables are used to represnt propositions

Question 7

List out 4 conventional letters used for propositional variables ( Notation )

Answer 7

1. p
2. q
3. r
4. s

Question 8

List out 2 values for truth value of proposition

Answer 8

1. True - T
2. False - F

Question 9

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

Answer 9

1. Not a proposition
2. Not a proposition
3. Not a proposition
   
   • Question doesn’t provide values for x , y and z
4. A proposition , True
5. A proposition , True

Question 10

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?

Answer 10

1. A proposition , True
2. A proposition , False (5 + 7 not equal to 10 )
3. Not a proposition
   
   • Question doesn’t provide values for x
4. A proposition , False (2 + 3 not equal to 4 )
5. Not a proposition
6. A proposition , False ( Cat isn’t an insect )
7. Not a proposition
8. Not a proposition

Question 11

What are compound compositions?

Answer 11

1. Mathematical statements are constructed by combining one or more propositions

• Formed from existing propositions using logical operators

Question 12

How are compound compositions formes?

Answer 12

1. From existing propositions using logical operators

Question 13

What does logical operations include?

Answer 13

1. Comparisons of 2 data

• Result will be either True or False

Question 14

How can logical operations be represented ?

Answer 14

1. Using truth table ( True - 1 , False - 0 )

Question 15

What determined the number of rows inside a truth table?

Answer 15

1. 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

Question 16

List out all 6 nouns for Logical Connectives

Answer 16

1. Negation
2. Conjunction
3. Disjunction
4. Exclusive Disjunction ( XOR )
5. Implication / Conditional
6. Biconditional

Question 17

What is the connectives and symbol for negation?

Answer 17

1. Connectives
   
   • not
2. Symbol
   
   • ~
   • ¬

• Think of it as a Not Gate

Question 18

What is the connectives and symbol for conjunction?

Answer 18

1. Connectives
   
   • and
   • but
2. Symbol
   
   • （ ^ ）

Question 19

What is the connectives and symbol for disjunction?

Answer 19

1. Connectives
   
   • or
2. Symbol
   
   • ∨

Question 20

What is the connectives and symbol for implication / conditional?

Answer 20

1. Connectives
   
   • if .. (p) .. then only .. (q) ..
2. Symbol
   
   • p → q

Question 21

What is the connectives and symbol for exclusive disjunction?

Answer 21

1. Connectives
   
   • exclusive or ( xor )
2. Symbol
   
   • ⊕

Question 22

What is the connectives and symbol for negation?

Answer 22

1. Connectives
   
   • if ..(p).. and only if ..(q)..
2. Symbol
   
   • p ↔ q

Question 23

List out the truth table of Negation

Answer 23

p ¬p
T F
F T

• Not Gate
• It is the statement “It is not the case that p”
• Opposite truth value of p

Question 24

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

Answer 24

1. Today is not Friday
2. Less than 10 inches of rain fell today in Miami
   
   • At Least ( > 10 ) , Negation Less than ( 10 < )
3. 1 + 1 ≠ 2
4. Lions can fly
5. I will not study hard, and I will pass this course
6. = ~ ( 1 + 2 = 3 ) and ~ ( 2 + 1 = 3 )
   = 1 + 2 ≠ 3 and 2 + 1 ≠ 3

Question 25

What are 2 keywords that is being used inside conjunction?

Answer 25

1. But ( Sometimes used instead of and ) 2. And

Question 26

What is the condition of conjunction?

Answer 26

1. p and q ( p ^ q ) when **both** p and q are **true**

Question 27

Construct the truth table of conjunction

Answer 27

p q p ^ q T T T T F F F T F F F F

Question 28

What are the keywords in disjunction?

Answer 28

1. or

Question 29

What is the condition of disjunction?

Answer 29

1. p or q **( p ∨ q )** is **false** when both p and q are **false**

Question 30

Construct a truth table for disjunction

Answer 30

p q p ∨ q T T T T F T F T T F F F

Question 31

What is the keywords for exclusice disjunction?

Answer 31

1. exclusive or * p or q but not both

Question 32

What is the condition for exclusive disjunction?

Answer 32

1. 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

Question 33

Construct a truth table for exclusive disjunction

Answer 33

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!

Question 34

What is the keyword for expression implication ( conditional ) ? ( 8 )

Answer 34

**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

Question 35

What is the condition for implication?

Answer 35

1. 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

Question 36

Construct truth table for implication

Answer 36

p q p→q T T T **T F F** F T T F F F

Question 37

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

Answer 37

1. If Maria learns discrete mathematics, then she will find a good job 2. Maria will find a good job when she learns discrete mathematics 3. For Maria to get a good job, it is sufficient for her to learn discrete mathematics

Question 38

What is the keyword for expressing biconditional?

Answer 38

1. p if only if q 2. p iff q 3. If p then q, and conversely 4. p is necessary and sufficient for q

Question 39

What is the condition for biconditional?

Answer 39

1. 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

Question 40

Construct a truth table for biconditional

Answer 40

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

Question 41

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

Answer 41

1. False 2. False 3. True 4. True 13^2 = 169 5. a^4 . a^3 = a^ ( 4 + 3 ) = a^7

Question 42

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"

Answer 42

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

Question 43

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"

Answer 43

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

Question 44

Transform logical expressions to English sentences p : Alice is smart q : Alice is honest 1. ~p ^ q 2. p ∨ ( ~p ^ q ) 3. p → ~q

Answer 44

1. Alice is not smart but honest 2. Either Alice is smart or she is not smart but honest 3. If Alice is smart, then she is not honest

Question 45

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

Answer 45

1. ~q → p

Question 46

List out the precedence ( priority ) of operators in symbols ( Top to bottom )

Answer 46

1. ~ 2. ^ ( And ) 3. ∨ ( Or ) 4. → ( Conditional ) 5. ↔ ( Biconditional )

Question 47

What does logical equivalent ( ≡ ) represents ?

Answer 47

1. 2 statements ( Left & Right ) have the same **Truth Table** in all possible cases

Question 48

List out 3 logical equivalence statement

Answer 48

1. Tautology - Truth value in all possible cases is **True** 2. Contradiction - Truth value in all possible cases is **False** 3. Contigency / Indeterminant - Truth value in all possible cases is **Some True and False**

Question 49

Prove that p ∨ q ≡ ~ ( ~p ^ ~q )

Answer 49

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

Question 50

Construct a truth table and state whether it is tautology, contradiction or contingency 1. ( A ∨ B ) ^ ( ~A )

Answer 50

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

Question 51

What does computer used to represent information?

Answer 51

1. bits

Question 52

What is the possible value for bits?

Answer 52

1. 0 2. 1 * Since bit is called binary digit

Question 53

What is the rule of precedence of Boolean Algebra?

Answer 53

1. Parentheses / Brackets 2. Complement ( NOT ) 3. Product ( AND ) 4. Sum ( OR )

Question 54

Show that ( 1' . 0' ) + ( 1 . 0' ) = 1

Answer 54

( 1' . 0' ) + ( 1 . 0' ) = ( 0 . 1 ) + ( 1 . 1 ) = 0 + 1 = 1

Question 55

What is NOT gate also known as?

Answer 55

1. Inverter

Question 56

List out the truth table for NOT gate

Answer 56

A A' 0 1 1 0 _ A

Question 57

List out what symbols used in the gate below: 1. AND Gate 2. OR Gate

Answer 57

1. A x B ( A . B ) 2. A + B

Question 58

List out the truth table for AND gate

Answer 58

A B A.B 0 0 0 0 1 0 1 0 0 1 1 1

Question 59

List out the truth table for OR Gate

Answer 59

A B A+B 0 0 0 0 1 1 1 0 1 1 1 1

Question 60

List out the truth table for NAND Gate

Answer 60

A B A.B (A.B)' 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0

Question 61

List out truth table for NOR Gate

Answer 61

A B A+B (A+B)' 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0

Question 62

List out truth table for XOR Gate

Answer 62

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

Question 63

Write out truth table for p q r

Answer 63

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

Question 64

List out truth table for p q

Answer 64

p q T T T F F T F F 1st Column T T F F 2nd Column T F T F

Question 65

List out 2 standard for representing combinational logic

Answer 65

1. Sum-of-Product ( SOP ) 2. Product-of-Sums ( POS )

Question 66

What does SOP and POS also known as?

Answer 66

1. SOP - Minterm 2. POS - Maxterm

Question 67

What value that SOP ( Minterm ) evaluate?

Answer 67

1. When the function is 1 x y z F 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 x'y'z + zyz' + xyz = 1 ( Sum will be 1 ) xyz ( Product ) Sum of Product means sum ( + ) of the product xy + xz x' , when column x is 0 x , when column x is 1

Question 68

What value that POS ( Maxterm ) evaluate?

Answer 68

1. When the function is 0 x y z F 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 1 1 1 0 (x + y + z') (x' + y' + z) (x' + y' + z') = 0 ( Product will be 0 ) x+y+z ( Sum ) Product of Sum means product ( x ) of the sum xz x xy **x' , when column x is 1** **x , when column x is 0**

Question 69

Draw out K-Maps for 1. 2 Variables 2. 3 Variables

Answer 69

1. A\B 0 ( B' ) 1 ( B ) 0 ( A' ) 1 ( A ) 3. C\AB 00 ( A'B' ) 01 ( A'B ) 11 ( AB ) 10 (AB') 0 ( C' ) 1 ( C ) **Important** **00 , 01 , 11, 10 for 3 - 4 Variables**

Question 70

List out rules for K-Map ( 6 )

Answer 70

1. Containing total number of 1 in a power of 2 [ 1 1 ] [ 1 ] [ 1 1 ] [ 1 ] 2. Must be in the same row ( Cannot be diagonal ) 3. Must be as large as possible ( If can go to 4 , just go to 4 , don't take it 2 2 ) 5. Using fewest block to combine the 1 6. Overlapping is allowed

Question 71

List out 5 steps for doing K-Maps

Answer 71

1. Select K-Map according to the number of variables 2. Put 1 in Cells of K-Map respective to the minterms 3. Make rectangular blocks ( Follow the rules ) 4. Examine each block, identify the common variable and discard the variable that differs within each block 5. Sum the product term obtained from each block in step 4 C \AB 00 01 11 10 0 1 1 1 1 1 1 1 Step 4 : Find Common C \AB 00 0 1 Common : A'B' ( Both 000 and 001 has 1 1 00 in common ) C \AB 00 01 11 10 0 1 1 1 1 1 Common : A Step 5 : Sum in Step 4 A'B' + A