X


Logic and Bit Operations




Q. Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101.




Translating English Sentences




Q. How can this English sentence be translated into a logical expression? “You can access the Internet from campus only if you are a computer science major or you are not a freshman.”



Q. How can this English sentence be translated into a logical expression? “You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”





Q. Express the specification “The automated reply cannot be sent when the file system is full” using logical connectives.


Note : System specifications should be consistent, that is, they should not contain conflicting requirements that could be used to derive a contradiction. When specifications are not consistent, there would be no way to develop a system that satisfies all specifications.


Q. Determine whether these system specifications are consistent:
“The diagnostic message is stored in the buffer or it is retransmitted.”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic message is stored in the buffer, then it is retransmitted.”



Q. Determine whether these system specifications are consistent:
“The diagnostic message is stored in the buffer or it is retransmitted.”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic message is stored in the buffer, then it is retransmitted.”
“The diagnostic message is not retransmitted”





Q. Smullyan posed many puzzles about an island that has two kinds of inhabitants, knights, who always tell the truth, and their opposites, knaves, who always lie. You encounter two people A and B. What are A and B if A says “B is a knight” and B says “The two of us are opposite types?



Q. A father tells his two children, a boy and a girl, to play in their backyard without getting dirty. However, while playing, both children get mud on their foreheads. When the children stop playing, the father says “At least one of you has a muddy forehead,” and then asks the children to answer “Yes” or “No” to the question: “Do you know whether you have a muddy forehead?” The father asks this question twice. What will the children answer each time this question is asked, assuming that a child can see whether his or her sibling has a muddy forehead, but cannot see his or her own forehead? Assume that both children are honest and that the children answer each question simultaneously





Logic Circuits



Q. Determine the output for the combinatorial circuit in Figure



Q. Build a digital circuit that produces the output (p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r)) when given input bits p, q, and r.






Propositional Equivalences




Tautology





Q. Construct examples of tautologies and contradictions using just one propositional variable.



Logical Equivalences





Q. Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent.



NOTE : 2n rows are required if a compound proposition involves 'n' propositional variables






Logical Equivalences



EquivalenceName
p ∧ T ≡ p ; p ∨ F ≡ p Identity laws
p ∨ T ≡ T ; p ∧ F ≡ F Domination laws
p ∨ p ≡ p ; p ∧ p ≡ p Idempotent laws
¬(¬p) ≡ p Double negation law
p ∨ q ≡ q ∨ p ; p ∧ q ≡ q ∧ p Commutative laws
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) ; (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Associative laws
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) ; p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) Distributive laws
¬(p ∧ q) ≡ ¬p ∨ ¬q ; ¬(p ∨ q) ≡ ¬p ∧ ¬q De Morgan’s laws
p ∨ (p ∧ q) ≡ p ; p ∧ (p ∨ q) ≡ p Absorption laws
p ∨ ¬p ≡ T ; p ∧ ¬p ≡ F Negation laws




Logical Equivalences Involving Conditional Statements.





Logical Equivalences Involving Biconditional Statements.






Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer” and “Heather will go to the concert or Steve will go to the concert.”


Previous Next