Logic and Proofs for Electronics Engineering

Module 1 LOGIC & PROOFS Electronics Engineering Department Faculty of Engineering University of Santo Tomas Topics 1. Propositional Logic 2. Connectives 3. Truth Table 4. Validity of Arguments 5. Proofs 6. Logic Puzzle and Clever Logic 7. Logic Circuit Application INT...

Module 1 LOGIC & PROOFS Electronics Engineering Department Faculty of Engineering University of Santo Tomas Topics 1. Propositional Logic 2. Connectives 3. Truth Table 4. Validity of Arguments 5. Proofs 6. Logic Puzzle and Clever Logic 7. Logic Circuit Application INTRODUCTION WHAT WILL YOU DO? You are lost and alone in the woods. You stumble across an old cabin and decided to stay there for a night. You want some heat and light, but the only things you find in the cabin are a candle, an oil lamp, and a wood burning stove. You look in your pocket, but you only have one match left. What do you light first? earoxas©2012|engrcde©2017 INTRODUCTION WHAT DO YOU SAY? What do you say? Do you say, “Nine and five is thirteen”, or “Nine and five are thirteen”? earoxas©2012|engrcde©2017 INTRODUCTION WHO’S RIGHT? Determine the validity of the given argument: “If the man is right and the woman is wrong, then the woman is right. If the man is wrong and the woman is right, then the woman is right. If the man is wrong and the woman is wrong, then the woman is right. If the man is right and the woman is right, then the woman is right. Therefore, women are always right.” earoxas©2012|engrcde©2017  LOGIC PROPOSITIONAL LOGIC Logic is the study of reasoning. The rules of logic are used to distinguish between valid and invalid mathematical arguments. These rules can be also applied in the design and verification of computer programs. Consequently, propositions are sentences or expressions that are not arbitrary but are the ones that are either true or false, but not both. earoxas©2012|engrcde©2017  LOGIC PROPOSITIONAL LOGIC Example No. 1: Identify which of the following sentences or expressions are propositions. a. The capital of the Philippines f. There are 53 cards in a deck. is Manila. g. 2+5=7 b. 8 is a prime number. h. 2+2=5 c. x+2=3 i. Answer the following questions d. What is a truth table? completely. e. This statement is false. j. n is an odd number. earoxas©2012|engrcde©2017  LOGIC PROPOSITIONAL LOGIC Propositional logic is a mathematical model that allows us to reason about the truth and falsehood of logical expressions. Similarly, propositional calculus is the area of logic that deals with propositions. It is developed by the Greek Philosopher Aristotle. The methods of producing new propositions from existing ones were discussed by an English Mathematician George Boole in his book The Laws of Thought. earoxas©2012|engrcde©2017  LOGIC PROPOSITIONAL LOGIC Letters are used to denote propositional variables. Usually, the propositional variables used are p, q, r, and s. The capital of the Philippines is Manila. T (PROPOSITION) (TRUTH VALUE) There are 53 cards in a deck. F (PROPOSITION) (TRUTH VALUE) A proposition can be associated with a truth value. The truth value of a proposition is T for True and F for False. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Logical Connectives or Operators are used to build complex or compound propositions from simpler ones. A logical operator is either a unary operator, meaning it is applied to only a single proposition; or a binary operator, meaning it is applied to two propositions. An example of a unary operator is negation whereas binary operators can be in a form of a conjunction, disjunction, exclusive or, conditional, and biconditional. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Negation Operator A negation operator (~ or ¬) is a unary logical connective that takes the proposition p to another proposition which means not p. Hence, a negation operator changes a proposition’s truth value. It can also be read as, “it is not the case of p”. p: I took a bath this morning. T ~p: I didn’t take a bath this morning. F earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Conjunction Operator A conjunction operator (∧) is a binary logical connective that when applied to two propositions p and q will yield the proposition “p and q”. It is denoted by p∧q. The conjunction p∧q is the proposition that is true when both p and q are true and false otherwise. p: This book is interesting. q: I am staying home. p∧q : This book is interesting and I am staying home. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Disjunction Operator A disjunction operator (∨) is a binary logical connective that when applied to two propositions p and q will yield the proposition “p or q”. It is denoted by p∨q. The symbol ∨ is the abbreviation of the Latin word vel for the inclusive OR. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Disjunction Operator The disjunction p∨q is the proposition that is true when either p is true, q is true, or both are true, and is false otherwise. Hence, the or intended is an inclusive OR. p: I took a bath this morning. q: I just washed my hair. p∨q : I took a bath this morning or just washed my hair. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Exclusive OR Operator Exclusive OR (⊕) is a binary logical connective that when applied to two propositions p and q will yield the proposition “p xor q”. It is denoted by p⊕q. The exclusive OR p⊕q is the proposition that is true if exactly one of p or q is true, but not both. It is false if both are true or false. p: The appetizer is soup. q: The appetizer is salad. p⊕q : The appetizer is either soup or salad, but not both. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Conditional Operator A conditional or implication operator (à) is a binary logical connective that when applied to two propositions p and q will yield the proposition “if p then q”. It is denoted by pàq. In a conditional proposition, p is called the premise, hypothesis, or antecedent; q is called the conclusion or consequent. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Conditional Operator The implication pàq is the proposition that is false precisely when p is true but q is false. p: Meet me after lunch. (PREMISE) q: I am treating you to a dessert. (CONCLUSION) pàq: If you meet me after lunch, then I am treating you to a dessert. Meaning, if the premise is satisfied then it follows that the conclusion should happen or be achieved. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Conditional Operator There are other forms of conditional proposition aside from “if p then q”. It is also equivalent to the following: p implies q p only if q p is a sufficient condition for q q if p q whenever p q is a necessary condition for p earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Sufficient Condition A sufficient condition is a condition that suffices to guarantee a particular outcome. If the condition does not hold, the outcome might be achieved in another way, or not be achieved at all. But if the condition does hold, the outcome is guaranteed. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Sufficient Condition If I pour a gallon of freezing water on you, then you’ll wake up from your deep slumber. If rain pours from the sky, then the ground will be wet. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Necessary Condition A necessary condition is a condition that is necessary for a particular outcome to be achieved. The assertion that q is necessary for p is equivalent to “p cannot be true unless q is true” or “if q is false, then p is false”. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Necessary Condition If a human being is alive, then that human being has air to breathe. If someone sees viruses, then that person uses a microscope. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Rearrangements of an Implication Implications can be rearranged without changing the validity of the statements. The implication pàq can be rewritten into any of these three forms: Inverse Converse Contrapositive ~pà~q qàp ~qà~p earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Rearrangements of an Implication The implication “If you meet me after lunch, then I am treating you to a dessert”, can be rewritten into any of these forms. Inverse: If you don’t meet me after lunch, then I am not treating you to a dessert. Converse: If I am treating you to a dessert, then meet me after lunch. Contrapositive: If I am not treating you to a dessert, then don’t meet me after lunch. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Biconditional Operator A biconditional or material equivalence operator (↔) is a binary logical connective that when applied to two propositions p and q will yield the proposition “p if and only if q”. It is denoted by p↔q. For p↔q to be true, p and q should be both true or both false. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Biconditional Operator The biconditional statement is equivalent to (pàq)∧(qàp). Hence, in order to prove a biconditional statement, it is often break down into two parts: proving the implication pàq and proving the converse qàp. p: You passed the subject. q: Your raw average is 60% or higher. p↔q : You passed the subject if and only if your raw average is 60% or higher. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Biconditional Operator There are other forms of biconditional proposition aside from “p if and only if q”. It is also equivalent to the following: p is equivalent to q p is a necessary and sufficient condition for q earoxas©2012|engrcde©2017 PROPOSITIONAL LOGIC LOGICAL CONNECTIVES Table 1. Summary of Logical Connectives Logical Connective Symbol Expression Negation ~ or ¬ ~p Conjunction ∧ p∧ q Disjunction (Inclusive OR) ∨ p∨ q Exclusive OR ⊕ p⊕ q Conditional à pàq Biconditional ↔ p↔ q earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC TRUTH TABLES Truth tables represent the relationship between the truth values of propositions and the formed compound propositions using logical connectives or operators. It is a list of all the possible combinations and their corresponding output truth value once evaluated. Where: 𝒏 = 𝟐𝒌 k = number of input propositional variables n = total number of possible combinations earoxas©2012|engrcde©2017 PROPOSITIONAL LOGIC TRUTH TABLES Table 3. Truth table for Table 4. Truth table for Conjunction Disjunction Table 2. Truth table for Negation p q p∧ q p q p∨ q p ~p F F F F F F F T F T F F T T T F T F F T F T Note: A negation operator T T T T T T changes a proposition’s truth value Note: The conjunction p∧q is the Note: The disjunction p∨q is the proposition that is true when both p proposition that is true when either p and q are true and false otherwise. is true, q is true, or both are true, and is false otherwise. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC TRUTH TABLES Table 5. Truth table for Table 6. Truth table for Table 7. Truth table for Exclusive OR Implication Biconditional p q p⊕ q p q pà q p q p↔q F F F F F T F F T F T T F T T F T F T F T T F F T F F T T F T T T T T T Note: The exclusive OR p⊕q is the Note: The implication pàq is the Note: For p↔q to be true, p and q proposition that is true if exactly one of proposition that is false precisely should be both true or both false. p or q is true, but not both. It is false if when p is true but q is false. both are true or false. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 1. Given the propositions below, determine its equivalent conditional, inverse, converse, and contrapositive statements. p: I am elected President. q: I will lower taxes. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 2. Given the propositions below, determine its equivalent biconditional statement. p: I am indoors. q: It is raining outside. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 3. Given the following compound propositions below, translate them to their equivalent symbolic notation. a. If Esmie doesn’t come to get the menu, Claire will. b. If I am going to eat in that restaurant, I will eat fish. But if I go to another restaurant, I will have steak. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 4. Evaluate the compound proposition below. If I am going to eat in a restaurant, I will eat fish. But if I go to another restaurant, I will have steak. Assume the following propositional variables and truth values: p: I am going to eat in a restaurant. -False q: I am going to eat fish. -True r: I am going to eat steak. -False earoxas©2012|engrcde©2017 PROPOSITIONAL LOGIC SAMPLE PROBLEMS Table 8. Order of Operations Logical Connective Symbol Order Negation ~ or ¬ First Conjunction ∧ Second Disjunction (Inclusive OR) ∨ Third Exclusive OR ⊕ Third Conditional à Fourth Biconditional ↔ Last Note: To evaluate compound propositions, there is a hierarchy or order in doing so. Parenthesis can be used to change the order. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS An argument is composed of a sequence of statements called premise and a statement called conclusion. Logic seeks to discover the valid forms, the forms that make arguments valid. A form of argument is valid if and only if the conclusion is true under all interpretations of that argument in which the premises are true. A statement form can be shown to be a logical truth by either showing that it is a tautology or by means of a proof procedure. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS Tautology is an important class of compound propositions that are always true for all possible combinations of truth values of propositional variables. Contradiction or absurdity is the opposite of tautology. It is a compound proposition that is always false. If a compound proposition is neither a tautology or contradiction, it is classified as a contingency. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS An argument is said to be valid if and only if it is true in all interpretations or is a tautology. If my program won’t compile, then it produces a division by zero error. My program won’t compile. Therefore, it produces a division by zero error. Let the following representations: p: My program won’t compile. q: My program produces a division by zero error. earoxas©2012|engrcde©2017 PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS If my program won’t compile, then it produces a division by zero error. My program won’t compile. Therefore, it produces a division by zero error. Let the following representations: p: My program won’t compile. PREMISES q: My program produces a division by zero error. ((pàq)∧p)àq earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS To verify if the argument is valid, once evaluated, it should be true in all possible input combinations. Table 10. Truth Table for the Given Example p q pà q (pà q)∧ p ((pà q)∧ p)à q ((pàq)∧p)àq F F T F T F T T F T Therefore, the given T F F F T argument is VALID. T T T T T earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 5. Determine which of the following logical notations is a tautology, contradiction, or contingency. a. pàp e. (p∧~q)∧(~p∨q) b. ~p∨p f. (pàq)↔(~qà~p) c. ~(Aà(~AàB)) g. ((pàq)∧p)àq d. (p∧(pàq))àq h. Aà(~A↔(AàB)) earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 6. Prove the validity of the given argument. The competition will start on time implies that all contestants are present; if and only if the contestants are present or the competition will not start on time. Let the following representations: p: The competition will start on time. q: All the contestants are present. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 7. Given the following propositions and compound propositions, prove the validity of x∧y∧zàq. Let the following representations: p: Claire studies. q: Claire plays volleyball. r: Claire passes the board examination. x: If Claire studies, then she will pass the board exam. y: If Claire doesn’t play volleyball, she will study. z: Claire failed the examination. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 8. Show that the value of R which is equivalent to Aà(A∧B) is a contingent. 9. If AàB is false, determine the truth value of ~A∨(A↔B). earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC SAMPLE PROBLEMS 10.Determine the validity of the given argument: If the man is right and the woman is wrong, then the woman is right. If the man is wrong and the woman is right, then the woman is right. If the man is wrong and the woman is wrong, then the woman is right. If the man is right and the woman is right, then the woman is right. Therefore, women are always right. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS Compound values that have the same truth values in all possible combinations are called logically equivalent. If this is the case, then p↔q is a tautology. The notation p≡q denotes that p and q are logically equivalent. The symbol ≡ is not a logical connective, but rather, it is a statement that says that p↔q is a tautology. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS Let’s try to prove that (A∨B)∧~(~A∧B) is logically equivalent to A. To prove their equivalence, (A∨B)∧~(~A∧B) ↔A should be a tautology. Table 11. Truth Table for the Given Example A B A∨ B ~A ~A∧ B ~(~A∧ B) (A∨ B) ∧ ~(~A∧ B) (A∨ B) ∧ ~(~A∧ B)↔A F F F T F T F T F T T T T F F T T F T F F T T T T T T F F T T T earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS Table 12. Logical Equivalence p∧T≡p p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Identity Laws Distributive Laws p∨F≡p p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p∨T≡T ~(p ∨ q) ≡ ~p ∧ ~q Domination Laws De Morgan’s Law p∧F≡F ~(p ∧ q) ≡ ~p ∨ ~q p∨p≡p p ∨ (p ∧ q) ≡ p Idempotent Laws Absorption Laws p∧p≡p p ∧ (p ∨ q) ≡ p Double Negation p ∨ ~p ≡ T ~(~p) ≡ p Negation Laws Law p ∧ ~p ≡ F p∨q≡q∨p Commutative Laws pà q ≡ ~p ∨ q Definition of Implication p∧q≡q∧p (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative Laws p↔q ≡ (pà q) ∧ (qà p) Definition of Biconditional (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS Rules of inference pertains to rules that can be used as building blocks to construct more complicated valid arguments. The tautology (p∧(pàq))àq is the basis of the first rule of inference called modus ponens or law of detachment. Modus ponens is Latin for method of affirming. pàq If it is snowing today, then we will go skiing. p It is snowing today. ∴q Therefore, we will go skiing. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS The tautology ((pàq)∧(qàr))à(pàr) is the basis of the second rule of inference called hypothetical syllogism. pàq If it rains today, then we will not have a barbeque party. qàr If we do not have a barbeque party, then we will have a barbeque tomorrow. ∴pàr Therefore, if it rains today, we will have a barbeque tomorrow. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC VALIDITY OF ARGUMENTS The tautology ((pàq)∧~q))à~p is the basis of the third rule of inference called modus tollens. Modus tollens is Latin for method of denying. pàq If Claire is elected president of Math Club, then Jacob will be a member of the said club. ~q Jacob did not wish to become a member of the club. ∴~p Therefore, Claire is not elected president of the Math Club. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC PROOFS A proof is a valid argument that establishes the truth of a mathematical statement or the truth of a theorem. It can use hypotheses of the theorem, if there’s any, axioms assumed to be true, and previously proven theorems. In this module, direct, vacuous, and trivial proofs will be discussed. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC PROOFS Direct Proof A direct proof shows that a conditional statement pàq is true by showing that if p is true, then q must also be true; so that the combination p is true and q is false never occurs. In direct proof, p is assumed as true; and use axioms, definitions, previously proven theorems, together with rules of inference, to show that q must also be true. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC PROOFS Direct Proof Give a direct proof of the theorem, “If n is an odd integer, then n2 is odd.” Definition: The integer n is even if there exist an integer k such that n = 2k, and n is odd if there exist an integer k such that n = 2k + 1. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC PROOFS Direct Proof Give a direct proof of the theorem, “If m and n are both perfect squares, then nm is also a perfect square.” Definition: An integer a is a perfect square if there is an integer b such that a=b2. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC PROOFS Vacuous Proof To quickly prove that a conditional Table 6. Truth table for Implication statement pàq is true, it should be known p q pà q that p is false. Because in this case, pàq F F T must be true when p is false. F T T Consequently, if it can be shown that T F F p is false, then we have a proof which is T T T called vacuous proof. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC PROOFS Trivial Proof To quickly prove that a conditional Table 6. Truth table for Implication statement pàq is true, it should be known p q pà q that q is true. Because in this case, pàq F F T must be true when q is true. F T T Consequently, if it can be shown that T F F q is true, then we have a proof which is T T T called trivial proof. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Logic puzzles are puzzles that can be solved using logical reasoning. Solving logic puzzles is an excellent way to practice working with rules of logic. Also, computer programs designed to carry out logical reasoning often use well-known logic puzzles to illustrate their capabilities. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 1: Tony and his girlfriend Pepper, together with some members of S.H.I.E.L.D such as Bruce, Natasha, and their leader Nick, was in a room when a sudden power interruption occurred. When the power was restored, Nick was found murdered. An inquiry was held by the authority and these are their statements. earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 1: Bruce: I am innocent; Natasha was talking to Nick when the power was interrupted. Natasha: I am innocent; I was not talking to Nick when the power was out. Tony: I am innocent; Pepper committed the murder. Pepper: I am innocent; One of the men committed the murder. Four of these statements are true and four are false. Assuming only one person committed the murder, who did it? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 2: Boy, Ogie, and Cristy are suspected of income tax evasion. They testify under oath as follows: Boy: Ogie is guilty and Cristy is innocent. Ogie: If Boy is guilty, then so is Cristy. Cristy: I am innocent, but at least one of the others is guilty. Assuming everybody told the truth, who is/are innocent and guilty? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 3: If 3 cats can kill 3 rats in 3 minutes, how long will it take 100 cats to kill 100 rats? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 4: A little Indian and big Indian are walking down a path. The little Indian is the big Indian’s son. The big Indian is not the little Indian’s father? Who is it? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 5: A monkey is at the bottom of a 30 ft well. Each day he jumps three feet and slips back two. When will the monkey reach the top of the well? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 6: The number of eggs in a basket doubles every minute. The basket is full of eggs in an hour. When was the basket half full? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 7: A boat will carry only two hundred pounds. How may a man weighing 200 pounds and his sons, each of whom weighs 100 pounds, use it to cross the river? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 8: Raking my lawn, I heap up 22 big piles of leaves in the front yard and 39 in the back yard. If I put them together, how many piles will I have? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 9: A doctor gave you three pills and told you to take every half an hour. How long will the pill last? earoxas©2012|engrcde©2017  PROPOSITIONAL LOGIC LOGIC PUZZLES & CLEVER LOGIC Puzzle No. 10: Only one statement is true, which is it? One statement is false. Two statements are false. Three statements are false. Four statements are false. earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Logic gates are the basic building blocks of any digital system. It is an electronic circuit having one or more than one input and only one output. The relationship between the input and output is based on a certain logic. Based on this, logic gates are named as AND gate, OR gate, NOT gate, etc. Compound propositions or the logical language used in mathematics can be translated to circuits. earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Logical arguments are a combination of propositions, and circuits are a combination of switches that control the flow of current. Modern computers not only store data in the form of ‘0’s and ‘1’s, but also perform simple and complex tasks. Studying the relation between truth tables and circuits will help us understand the underlying principles behind the design and programming of computers. earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION In electronics engineering, a bit or binary digit is a basic unit of information used in computing and digital communications. It has two possible values: a zero (0) which represents a false value, and a one (1) which represents a true value. Bit 0 can also be called as a low logic level signal, whereas bit 1 can also be called as a high logic level signal. earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Inverter or NOT Gate Logical Operation: NOT, Inversion, Complementation, Negation It changes the value of a given bit from 1 to 0, or from 0 to 1. Table 12. Truth table for NOT Gate X Y X Y 0 1 INVERTER 1 0 ( = 𝑿′ Logical Expression: 𝒀 = 𝑿 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION AND Gate Logical Operation: AND, Logical Multiplication, Conjunction The output is high if and only if both inputs are high. Otherwise, the output is low. Table 13. Truth table for AND Gate X1 X2 Y X1 Y = X1X2 0 0 0 X2 0 1 0 1 0 0 Logical Expression: 𝒀 = 𝑿𝟏 + 𝑿𝟐 … 𝑿𝒏 1 1 1 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION OR Gate Logical Operation: OR, Logical Addition, Disjunction The output is high if either inputs are high, or both. Otherwise, the output is low. Table 14. Truth table for OR Gate X1 X2 Y X1 Y = X1 + X2 0 0 0 X2 0 1 1 1 0 1 Logical Expression: 𝒀 = 𝑿𝟏 + 𝑿𝟐 + ⋯ + 𝑿𝒏 1 1 1 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION XOR Gate Logical Operation: Exclusive OR (Inequality) The output is high if exactly one input is high. Otherwise, the output is low. Table 15. Truth table for XOR Gate X1 X2 Y X1 𝒀 = 𝑿𝟏 ⊕ 𝑿𝟐 0 0 0 X2 0 1 1 1 0 1 Logical Expression: 𝒀 = 𝑿𝟏 ⊕ 𝑿𝟐 ⊕ ⋯ ⊕ 𝑿𝒏 1 1 0 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION XNOR Gate Logical Operation: Exclusive-NOR, Biconditional (Equality) The output is high if exactly both inputs have the same logic level. Otherwise, the output is low. Table 16. Truth table for XNOR Gate X1 X2 Y X1 𝒀 = 𝑿𝟏 ⊕ 𝑿𝟐 0 0 1 X2 0 1 0 1 0 0 Logical Expression: 𝒀 = 𝑿𝟏 ⊕ 𝑿𝟐 ⊕ ⋯ ⊕ 𝑿𝒏 1 1 1 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION A logic gate is an idealized or physical device implementing a Boolean function, ie. It performs a logical operation on one or more logic inputs and produces a single logic output.... Single-Input-Single-Output Multiple-Input-Single-Output earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Boolean algebra is an algebra that deals with binary variables and logic operations. A Boolean function is described by an algebraic expression called Boolean expression which consists of binary variables, the constants 0 and 1, and the logic operation symbols. Examine the given Boolean function and expression below: 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴 + 𝐵𝐶 + 𝐴𝐷𝐶 BOOLEAN FUNCTION BOOLEAN EXPRESSION earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Boolean Expression NOT GATE 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴 + 𝐵𝐶 + 𝐴𝐷𝐶 INPUT BINARY OR GATE AND GATE VARIABLES Fig. 1. Logic Circuit Implementation earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Table 17. Truth Table Boolean Expression A 0 B 0 C 0 D 0 (BC)’ 1 ADC 0 F 1 NOT GATE 0 0 0 1 1 0 1 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴 + 𝐵𝐶 + 𝐴𝐷𝐶 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 INPUT BINARY OR GATE AND GATE 0 1 1 0 0 0 0 VARIABLES 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 1. Translate the following Boolean expressions into logic circuits. a. Y = (ABC)’⋅D’ b. W = A’BC + AB’C + ABC’ + A’BC’ c. J = X⋅(X + Y)(X + Z)(Y + Z) d. D = (ab + c) ⊕ (b + c) e. Z = (A⊕B)’ + (BC)’ earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 2. Translate the given logic circuit into a Boolean function and expression. earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 3. Translate the given logic circuit into a Boolean function and expression. earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 4. Translate the given logic circuit into a Boolean function and expression. earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 5. Translate the given logic circuit into a Boolean function and expression. earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 6. Translate the given logic circuit into a Boolean function and expression. earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 7. Given the following bit strings, perform a bitwise OR, bitwise AND, and bitwise XOR. 011 101 101 111 001 110 earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 8. Derive all the possible outputs of the given Boolean functions and expressions below. a. F = xy + xy’ b. F = (x+y)(x+y’) c. F = xyz + x’y + xyz’ earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Table 18. Postulates and Theorems of Boolean Algebra x+0=x Identity Laws x + (y + z) = (x + y) + z Associative Laws x·1=x (Postulate 2) x · (y · z) = (x · y) · z (Theorem 4) x+1=1 Domination Laws x · (y + z) = x · y + x · z Distributive Laws x·0=0 (Theorem 2) x + y · z = (x+y) · (x+z) (Postulate 4) x+x=x Idempotent Laws (x + y)’ = x’ · y’ De Morgan’s Law x·x=x (Theorem 1) (x · y)’ = x’ + y’ (Theorem 5) Double Negation Law x+x·y=x Absorption Laws (x’)’ = x (Theorem 3, Involution) x · (x+y) = x (Theorem 6) x+y=y+x Commutative Laws x · x’ = 0 Negation Laws x·y=y·x (Postulate 3) x + x’ = 1 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Duality Principle Duality principle states that every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged. If the dual of an algebraic expression is desired, the OR and AND operators are simple interchanged and 1s are replaced by 0s and 0s by 1s. earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Boolean Expression NOT GATE 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴 + 𝐵𝐶 + 𝐴𝐷𝐶 INPUT BINARY OR GATE AND GATE VARIABLES Note: In this given expression, we implement it using three 2-input NAND gates, 1 inverter, and two 2-input OR gates. Fig. 1. Logic Circuit Implementation earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Simplification of Boolean Expression 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴 + 𝐵𝐶 + 𝐴𝐷𝐶 DISTRIBUTIVE LAW = 𝐴 1 + 𝐷𝐶 + 𝐵𝐶 DOMINATION LAW 𝑭 𝑨, 𝑩, 𝑪 = 𝑨 + 𝑩𝑪 Note: In this simplified expression, we implement it using one 2-input NAND gates, 1 inverter, and one 2-input OR Fig. 2. Simplified Logic Circuit gates. Implementation earoxas©2012|engrcde©2017 LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Table 17. Truth Table of the Original Expression A B C D (BC)’ ADC F 0 0 0 0 1 0 1 Table 18. Truth Table of the 0 0 0 1 1 0 1 Simplified Expression 0 0 1 0 1 0 1 A B C (BC)’ F 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 9. Simplify the given expressions using the postulates and theorems of Boolean Algebra. a. F = xy + xy’ b. F = (x+y)(x+y’) c. F = xyz + x’y + xyz’ earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Universal Gates Universal gates have the property of creating any logic gate or any Boolean expression by combing them. NOR and NAND gates are considered as universal gates. earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION NAND Gate Logical Operation: Not AND The output is low if and only if both inputs are high. Otherwise, the output is high. Table 19. Truth table for NAND Gate X1 X2 Y X1 Y = 𝑿𝟏𝑿𝟐 0 0 1 X2 0 1 1 1 0 1 Logical Expression: 𝒀 = 𝑿𝟏 𝑿𝟐 … 𝑿𝒏 1 1 0 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION NOR Gate Logical Operation: Not OR The output is high if and only if both inputs are low. Otherwise, the output is low. Table 20. Truth table for NOR Gate X1 X2 Y X1 Y = 𝑿𝟏 + 𝑿𝟐 0 0 1 X2 0 1 0 1 0 0 Logical Expression: 𝒀 = 𝑿𝟏 + 𝑿𝟐 + ⋯ + 𝑿𝒏 1 1 0 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Universal Gates A A’ A (A+A)’=A’ A A’ A (A’+B’)’=AB AB B B B’ A (A+B)’ (A+B)’’=A+B A+B A B B Fig. 3. Implementation of NOT, AND, and OR gates Using NOR gates earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Universal Gates A A’ A (AA)’=A’ A A’ A (A’B’)’=A+B AB B B B’ A (AB)’ (AB)’’=AB A+B A B B Fig. 3. Implementation of NOT, AND, and OR gates Using NAND gates earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 10.Implement the given expressions using universal gates (either using NOR or NAND gates). Determine the total number of universal gates used before and after simplification. a. F = xy + xy’ b. F = (x+y)(x+y’) c. F = xyz + x’y + xyz’ earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Canonical Forms of Boolean Functions Boolean functions expressed as sum of minterms or product of maxterms are said to be in canonical form. These two canonical forms can be obtained from reading a function from a truth table. Hence, in canonical forms, all input variables should appear. earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Canonical Forms of Boolean Functions Examine the given truth table below. Note that x and y are input variables and F represents the output. Derive the canonical form of F. Table 21. Truth Table of Function F x y F 0 0 0 0 1 0 𝑭 𝒙, 𝒚 =? 1 0 1 1 1 1 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Canonical Forms of Boolean Functions Table 21. Truth Table of Function F A Boolean function can be expressed x y F algebraically from a given truth table. 0 0 0 This is by forming a minterm or 0 1 0 standard product for each combination of 1 0 1 variables that produces a 1 in the output 1 1 1 and then taking the OR of all those terms. 𝑭 𝒙, 𝒚 = 𝒙𝒚/ + 𝒙𝒚 SUM OF MINTERMS earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Canonical Forms of Boolean Functions Table 21. Truth Table of Function F Another canonical form can be x y F obtained by forming a maxterm or 0 0 0 standard sum for each combination of 0 1 0 variables that produces a 0 in the output 1 0 1 and then taking the AND of all those 1 1 1 terms. 𝑭 𝒙, 𝒚 = (𝒙 + 𝒚)(𝒙 + 𝒚/ ) PRODUCT OF MAXTERMS earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Canonical Forms of Boolean Functions Examine the given Boolean function and expression below. Express it as sum of minterms and product of maxterms. Note that for a given expression to be considered as a canonical form, all input variables should appear in each term. 𝐹 𝑥, 𝑦, 𝑧 = 𝑥𝑧 + 𝑦′𝑧 y variable is x variable is missing missing earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Sum of Minterms 𝐹 𝑥, 𝑦, 𝑧 = 𝑥𝑧 + 𝑦′𝑧 𝐹 𝑥, 𝑦, 𝑧 = 𝑥𝑧(𝑦 + 𝑦 / ) + 𝑦′𝑧(𝑥 + 𝑥 / ) MULTIPLYING A 1 MULTIPLYING A 1 𝐹 𝑥, 𝑦, 𝑧 = 𝑥𝑦𝑧 + 𝑥𝑦 / 𝑧 + 𝑥𝑦′𝑧 + 𝑥 / 𝑦′𝑧 𝐹 𝑥, 𝑦, 𝑧 = 𝑥𝑦𝑧 + 𝑥𝑦 / 𝑧 + 𝑥 / 𝑦′𝑧 earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Product of Maxterms 𝐹 𝑥, 𝑦, 𝑧 = 𝑥𝑧 + 𝑦 # 𝑧 = 𝑎 + 𝑏𝑐 RECALL: Distributive Laws Let xz be x · (y + z) = x · y + x · z Let y’ be represented by b, and z represented by a be represented by c x + y · z = (x+y) · (x+z) 𝐹 𝑥, 𝑦, 𝑧 = (𝑥𝑧 + 𝑦 # )(𝑥𝑧 + 𝑧) 𝐹 𝑥, 𝑦, 𝑧 = (𝑦 # + 𝑥)(𝑦 # + 𝑧)(𝑧 + 𝑥)(𝑧 + 𝑧) 𝐹 𝑥, 𝑦, 𝑧 = (𝑦 # + 𝑥 + 𝑧𝑧′)(𝑦 # + 𝑧 + 𝑥𝑥′)(𝑧 + 𝑥 + 𝑦𝑦′)(𝑧 + 𝑥𝑥 # ) 𝐹 𝑥, 𝑦, 𝑧 = (𝑦 # + 𝑥 + 𝑧)(𝑦 # + 𝑥 + 𝑧′)(𝑦 # + 𝑧 + 𝑥)(𝑦 # + 𝑧 + 𝑥′)(𝑧 + 𝑥 + 𝑦) (𝑧 + 𝑥 + 𝑦′)(𝑧 + 𝑥)(𝑧 + 𝑥 # ) earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Product of Maxterms 𝐹 𝑥, 𝑦, 𝑧 = (𝑦 # + 𝑥 + 𝑧)(𝑦 # + 𝑥 + 𝑧′)(𝑦 # + 𝑧 + 𝑥)(𝑦 # + 𝑧 + 𝑥′)(𝑧 + 𝑥 + 𝑦) (𝑧 + 𝑥 + 𝑦′)(𝑧 + 𝑥)(𝑧 + 𝑥 # ) 𝐹 𝑥, 𝑦, 𝑧 = (𝑥 + 𝑦 # + 𝑧)(𝑥 +𝑦 # +𝑧′)(𝑥 + 𝑦 # + 𝑧)(𝑥′ +𝑦 # +𝑧)(𝑥 + 𝑦 + 𝑧) (𝑥 + 𝑦 # + 𝑧)(𝑧 + 𝑥 + 𝑦𝑦 # )(𝑧 + 𝑥′ + 𝑦𝑦′) 𝐹 𝑥, 𝑦, 𝑧 = (𝑥 + 𝑦 # + 𝑧)(𝑥 +𝑦 # +𝑧′)(𝑥 + 𝑦 # + 𝑧)(𝑥′ +𝑦 # +𝑧)(𝑥 + 𝑦 + 𝑧) (𝑥 + 𝑦 # + 𝑧)(𝑧 + 𝑥 + 𝑦)(𝑧 + 𝑥 + 𝑦 # )(𝑧 + 𝑥′ + 𝑦)(𝑧 + 𝑥′ + 𝑦′) 𝐹 𝑥, 𝑦, 𝑧 = (𝑥 + 𝑦 # + 𝑧)(𝑥 +𝑦 # +𝑧′)(𝑥′ +𝑦 # +𝑧)(𝑥 + 𝑦 + 𝑧)(𝑥′ + 𝑦 + 𝑧) earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Table 22. Term and Designation of a Three- Note: When a Boolean function is in its variable Boolean function as Sum of Minterms sum of minterms form, it is sometimes convenient to express the function in a brief notation. 𝐹 𝑥, 𝑦, 𝑧 = 𝑥𝑦𝑧 + 𝑥𝑦 / 𝑧 + 𝑥 / 𝑦′𝑧 𝐹 𝑥, 𝑦, 𝑧 = < 𝑚 (1,5,7) earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Table 23. Term and Designation of a Three- Note: When a Boolean function is in its variable Boolean function as Product of Maxterms product of maxterms form, it is sometimes convenient to express the function in a brief notation. 𝐹 𝑥, 𝑦, 𝑧 = 𝑥 + 𝑦 ! + 𝑧 𝑥 +𝑦 ! +𝑧 ! (𝑥′ +𝑦 ! +𝑧) (𝑥 + 𝑦 + 𝑧)(𝑥′ + 𝑦 + 𝑧) 𝐹 𝑥, 𝑦, 𝑧 = @ 𝑀 (0,2,3,4,6) earoxas©2012|engrcde©2017  LOGIC CIRCUITS LOGIC CIRCUIT APPLICATION Conversion Between Canonical Forms Minterm to Maxterm Conversion Identify the indices that don’t appear in sum of minterms and derive the indices for the product of maxterms. 𝑭 𝒙, 𝒚, 𝒛 = 1 𝒎 𝟏, 𝟓, 𝟕 = 6 𝑴 (𝟎, 𝟐, 𝟑, 𝟒, 𝟔) Maxterm to Minterm Conversion Identify the indices that don’t appear in product of maxterms and derive the indices for the sum of minterms. 𝑭 𝒙, 𝒚, 𝒛 = 6 𝑴 𝟎, 𝟐, 𝟑, 𝟒, 𝟔 = 1 𝒎 𝟏, 𝟓, 𝟕 earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 1. Express the given Boolean function as sum of minterms. F = A + B’C earoxas©2012|engrcde©2017  LOGIC CIRCUITS SAMPLE PROBLEMS 2. Express the given Boolean function as product of maxterms. F = xy + x’z earoxas©2012|engrcde©2017