Math 240

1.6 Rules of Inference

The Socrates Example • We have the two premises: ○ “All men are mortal.” ○ “Socrates is a man.” • And the conclusion: ○ “Socrates is mortal.” • How do we get the conclusion from the premises? The Argument • We can express the premises (above the line) and the conclusion (below the line) in predicate logic as an argument: • We will see shortly that this is a valid argument Arguments in Propositional Logic • An argument in propositional logic is a sequence of propositions. • All but the final proposition are called premises. • The last statement is the conclusion. • The argument is valid if the premises imply the conclusion. • An argument form is an argument that is valid no matter what propositions are substituted into its propositional variables. • If the premises are p_1, p_2, …,p_n and the conclusion is q then ○ (p_1∧p_2∧…∧p_n)→q is a tautology. • Inference rules are all argument simple argument forms that will be used to construct more complex argument forms. Rules of Inference for Propositional Logic: • Modus Ponens ○ Equation ○ Corresponding Tautology: § (p∧(p→q))→q ○ Example: § Let p be “It is snowing.” § Let q be “I will study discrete math. § “If it is snowing, then I will study discrete math.” § “It is snowing.” § “Therefore , I will study discrete math.” • Modus Tollens ○ Equation ○ Corresponding Tautology: § (¬q∧(p→q))→¬p ○ Example: § Let p be “it is snowing.” § Let q be “I will study discrete math.” § “If it is snowing, then I will study discrete math.” § “I will not study discrete math.” § “Therefore , it is not snowing.” • Hypothetical Syllogism ○ Equation ○ Corresponding Tautology: § ((p→q)∧(q→r))→(p→r) ○ Example: § Let p be “it snows.” § Let q be “I will study discrete math.” § Let r be “I will get an A.” § “If it snows, then I will study discrete math.” § “If I study discrete math, I will get an A.” § “Therefore , If it snows, I will get an A.” • Disjunctive Syllogism ○ Equation ○ Corresponding Tautology: § (¬p∧(p ∨q))→q ○ Example: § Let p be “I will study discrete math.” § Let q be “I will study English literature.” § “I will study discrete math or I will study English literature.” § “I will not study discrete math.” § “Therefore , I will study English literature.” • Addition ○ Equation ○ Corresponding Tautology: § p→(p ∨q) ○ Example: § Let p be “I will study discrete math.” § Let q be “I will visit Las Vegas.” § “I will study discrete math.” § “Therefore, I will study discrete math or I will visit Las Vegas.” • Simplification ○ Equation ○ Corresponding Tautology: § (p∧q)→p ○ Example: § Let p be “I will study discrete math.” § Let q be “I will study English literature.” § “I will study discrete math and English literature” § “Therefore, I will study discrete math.” • Conjunction ○ Equation ○ Corresponding Tautology: § ((p)∧(q))→(p∧q) ○ Example: § Let p be “I will study discrete math.” § Let q be “I will study English literature.” § “I will study discrete math.” § “I will study English literature.” § “Therefore, I will study discrete math and I will study English literature.” • Resolution ○ Equation ○ Corresponding Tautology: § ((¬p∨r)∧(p∨q))→(q ∨ r) ○ Example: § Let p be “I will study discrete math.” § Let r be “I will study English literature.” § Let q be “I will study databases.” § “I will not study discrete math or I will study English literature.” § “I will study discrete math or I will study databases.” § “Therefore, I will study databases or I will study English literature.” Using the Rules of Inference to Build Valid Arguments • A valid argument is a sequence of statements. • Each statement is either a premise or follows from previous statements by rules of inference. • The last statement is called conclusion. Valid Arguments Example 1 ○ From the single proposition p∧(p→q) ○ Show that q is a conclusion. Example 2 ○ With these hypotheses: § “It is not sunny this afternoon and it is colder than yesterday.” § “We will go swimming only if it is sunny.” § “If we do not go swimming, then we will take a canoe trip.” § “If we take a canoe trip, then we will be home by sunset.” ○ Using the inference rules, construct a valid argument for the conclusion: § “We will be home by sunset.” ○ Choose propositional variables: § p: “It is sunny this afternoon.” § r: “We will go swimming.” § t: “We will be home by sunset.” § q: “It is colder than yesterday.” § s: “We will take a canoe trip.” ○ Translation into propositional logic: § Hypotheses: ¬p∧q, r→p,¬r→s,s→t § Conclusion: t ○ Argument Handling Quantified Statements • Universal Instantiation (UI) ○ Example: § Our domain consists of all dogs and Fido is a dog. § “All dogs are cuddly.” § “Therefore, Fido is cuddly.” • Universal Generalization (UG) ○ Used often implicitly in Mathematical Proofs. • Existential Instantiation (EI) ○ Example: § “There is someone who got an A in the course.” § “Let’s call her a and say that a got an A” • Existential Generalization (EG) ○ Example: § “Michelle got an A in the class.” § “Therefore, someone got an A in the class.” Using Rules of Inference • Example 1 ○ Using the rules of inference, construct a valid argument to show that § “John Smith has two legs” ○ is a consequence of the premises § “Every man has two legs.” § “John Smith is a man.” ○ Notation and domain § Let M(x) denote “x is a man” § L(x) “x has two legs” § Let John Smith be a member of the domain. ○ Argument • Example 2 ○ Use the rules of inference to construct a valid argument showing that the conclusion § “Someone who passed the first exam has not read the book.” follows from the premises “A student in this class has not read the book.” “Everyone in this class passed the first exam.” ○ Notation § Let C(x) denote “x is in this class.” § B(x) denote “x has read the book.” § P(x) denote “x passed the first exam.” ○ First we translate the premises and conclusion into symbolic form. ○ Argument Returning to the Socrates Example • Premises and conclusion • Argument The Barber Example • Show that from the statements • Every barber in Jonesville shaves those and only those who don t shave themselves. and There is a barber in Jonesville • We can derive a contradiction ○ ∀x(B(x)→∀y(S(x,y)⟷¬S(y,y))) ○ ∃x B(x) ○ ∀c B(c) ○ B(c)→∀y(S(c,y)⟷¬S(y,y)) ○ ∀y (S(c,y)⟷¬S(y,y)) ○ S(c,c)⟷¬S(c,c) ○ Thus, we have a contradiction Lewis Carroll • The first three are called premises and the third is called the conclusion ○ “All hummingbirds are richly colored.” ○ “No large birds live on honey.” ○ “Birds that do not live on honey are dull in color.” ○ “Hummingbirds are small.” • Notation ○ H(x)≔x is a hummingbird ○ C(x)≔x is richly colored ○ L(x)≔x is large ○ Ho(x)≔x lives on honey • Here is one way to translate these statements to predicate logic ○ ∀x (H(x)→C(x)) ○ ∀x (L(x)→¬Ho(x)) ○ ∀x (¬Ho(x)→¬C(x)) ○ ∀x (H(x)→¬L(x)) • Let c be an arbilirary element of the universe (1) ∀x (H(x)→C(x)) (2) ∀x (L(x)→¬Ho(x)) (3) ∀x (¬Ho(x)→¬C(x)) (4) H(c)→C(c)≡¬H(c)∨C(c) (5) L(c)→¬Ho(c)≡¬L(c)∨¬Ho(c) (6) ¬Ho(c)→¬C(c)≡Ho(c)∨¬C(c) (7) By resolution of (4) and (6), ¬H(c)∨Ho(c) (8) By resolution of (5) and (7), ¬H(c)∨¬L(c)≡H(c)→¬L(c) (9) By (8), ∀x(H(x)→¬L(x))

Read More >>

1.5 Nested Quantifiers

Nested Quantifiers • Nested quantifiers are often necessary to express the meaning of sentences in English as well as important concepts in computer science and mathematics. • Example ○ “Every real number has an inverse” is ○ ∀x ∃y(x+y=0) ○ where the domains of x and y are the real numbers. • We can also think of nested propositional functions: ○ ∀x ∃y(x+y=0) can be viewed as ∀x Q(x) ○ where Q(x) is ∃y P(x, y) where P(x, y) is (x+y=0) Thinking of Nested Quantification • Nested Loops • To see if ∀x∀y P(x,y) is true, loop through the values of x: • At each step, loop through the values for y. • If for some pair of x and y, P(x,y) is false, then ∀x∀y P(x,y) is false and both the outer and inner loop terminate. • ∀x∀y P(x,y) is true if the outer loop ends after stepping through each x. • To see if ∀x∃y P(x,y) is true, loop through the values of x: • At each step, loop through the values for y. • The inner loop ends when a pair x and y is found such that P(x, y) is true. • If no y is found such that P(x, y) is true • the outer loop terminates as ∀x∃y P(x,y) has been shown to be false. • ∀x∃y P(x,y) is true if the outer loop ends after stepping through each x. • If the domains of the variables are infinite, • then this process cannot actually be carried out. Order of Quantifiers • Let P(x,y) be the statement “x+y=y+x.” • Assume that U is the real numbers. • Then ∀x∀y P(x,y) and ∀y∀x P(x,y) have the same truth value. • Let Q(x,y) be the statement “x+y=0.” • Assume that U is the real numbers. • Then ∀x∃y Q(x,y) is true, but ∃y∀x Q(x,y) is false. Questions on Order of Quantifiers • Example 1 ○ Let U be the real numbers, ○ Define P(x,y): x∙y=0 ○ ∀x∀yP(x,y)=F ○ ∀x∃yP(x,y)=T ○ ∃x∀yP(x,y)=T ○ ∃x∃yP(x,y)=T Example 2 ○ Let U be the positive real numbers, ○ Define P(x,y): x/y=1 ○ ∀x∀yP(x,y)=F ○ ∀x∃yP(x,y)=T ○ ∃x∀yP(x,y)=F ○ ∃x∃yP(x,y)=T Translating Nested Quantifiers into English • Example 1 ○ Translate the statement ∀x(C(x)∨∃y(C(y)∧F(x, y))) § where C(x) is “x has a computer,” § and F(x,y) is “x and y are friends,” § and the domain for both x and y consists of all students in your school. ○ Solution § Every student in your school has a computer or has a friend who has a computer. • Example 2 ○ Translate the statement § ∃x∀y∀z ((F(x, y)∧ F(x,z)∧(y ≠z))→¬F(y,z)) ○ Solution § There is a student none of whose friends are also friends with each other. • Example 3 ○ Translate the statement ∀x (B(x)∨∃y (B(y)∧S(y,x))) § Where B(x) is

Read More >>

1.4 Predicates and Quantifiers

Propositional Logic Not Enough • If we have: ○ “All men are mortal.” ○ “Socrates is a man.” • Does it follow that “Socrates is mortal?” • Can’t be represented in propositional logic. • Need a language that talks about objects, their properties, and their relations. • Later we’ll see how to draw inferences. Introducing Predicate Logic • Predicate logic uses the following new features: ○ Variables: x, y, z ○ Predicates: P(x), M(x) ○ Quantifiers: exists and for all • Propositional functions are a generalization of propositions. ○ They contain variables and a predicate, e.g., P(x) ○ Variables can be replaced by elements from their domain. Propositional Functions • Propositional functions become propositions (and have truth values) when their variables are each replaced by a value from the domain (or bound by a quantifier). • The statement P(x) is said to be the value of the propositional function P at x. • For example, let P(x) denote “x0” and the domain be the integers. Then: ○ P(−3) is false. ○ P(0) is false. ○ P(3) is true. • Often the domain is denoted by U. So in this example U is the integers. Examples of Propositional Functions • Let “x+y=z” be denoted by R(x, y, z) and U be the integers. • Find these truth values: ○ R(2,−1,5) =F ○ R(3,4,7)=T ○ R(x, 3, z)⇒ Not a Proposition • Now let “x is the least number” be denoted by Q(x), with U={0,1,2,3,5}. • Find these truth values: ○ Q(0)=T ○ Q(5)=F ○ Q(6)⇒ undefined • What is Q(0) is U is the integers? Q(0)=F Compound Expressions • Connectives from propositional logic carry over to predicate logic. • If P(x) denotes “x0,” find these truth values: ○ P(3)∨ P(−1)=T∨F=T ○ P(3)∨ P(−1)=T∧F=F ○ P(3)→P(−1)=T→F=F ○ P(3)→¬P(−1)=T→T=T • Expressions with variables are not propositions and therefore do not have truth values. For example, ○ P(3)∧P(y) ○ P(x)→P(y) • When used with quantifiers (to be introduced next), these expressions (propositional functions) become propositions. Quantifiers • We need quantifiers to express the meaning of English words including all and some: ○ “All men are Mortal.” ○ “Some cats do not have fur.” • The two most important quantifiers are: ○ Universal Quantifier, “For all,” symbol: ∀ ○ Existential Quantifier, “There exists,” symbol: ∃ • We write as in ∀x P(x) and ∃x P(x). ○ ∀x P(x) asserts P(x) is true for every x in the domain. ○ ∃x P(x) asserts P(x) is true for some x in the domain. • The quantifiers are said to bind the variable x in these expressions. Universal Quantifier • ∀x P(x) is read as “For all x, P(x)” or “For every x, P(x)” • If P(x) denotes “x0” and U is the integers, then ∀x P(x) is false. • If P(x) denotes “x0” and U is the positive integers, then ∀x P(x) is true. • If P(x) denotes “x is even” and U is the integers, then ∀x P(x) is false. Existential Quantifier • ∃x P(x) is read as “For some x, P(x)”, or as “There is an x such that P(x),” or “For at least one x, P(x).” • If P(x) denotes “x0” and U is the integers, then ∃x P(x) is true. It is also true if U is the positive integers. • If P(x) denotes “x0” and U is the positive integers, then ∃x P(x) is false. • If P(x) denotes “x is even” and U is the integers, then ∃x P(x) is true. Thinking about Quantifiers • When the domain of discourse is finite, we can think of quantification as looping through the elements of the domain. • To evaluate ∀x P(x) loop through all x in the domain. • If at every step P(x) is true, then ∀x P(x) is true. • If at a step P(x) is false, then ∀x P(x) is false and the loop terminates. • To evaluate ∃x P(x) loop through all x in the domain. • If at some step, P(x) is true, then ∃x P(x) is true and the loop terminates. • If the loop ends without finding an x for which P(x) is true, then ∃x P(x) is false. • Even if the domains are infinite, we can still think of the quantifiers this fashion, but the loops will not terminate in some cases. Thinking about Quantifiers as Conjunctions and Disjunctions • If the domain is finite, a universally quantified proposition is equivalent to a conjunction of propositions without quantifiers and an existentially quantified proposition is equivalent to a disjunction of propositions without quantifiers. • If U consists of the integers 1,2, and 3: ○ ∀x P(x)≡P(1)∧P(2)∧P(3) ○ ∃x P(x)≡P(1)∨P(2)∨P(3) • Even if the domains are infinite, you can still think of the quantifiers in this fashion, but the equivalent expressions without quantifiers will be infinitely long. Precedence of Quantifiers • The quantifiers ∀ and ∃ have higher precedence than all the logical operators. • For example, ∀x P(x)∨Q(x) means (∀x P(x))∨Q(x) • ∀x (P(x)∨Q(x)) means something different. Translating from English to Logic • Every student in this class has taken a course in Java. ○ Solution 1 § If U=every student in the class § Let J(x)≔x has taken a course in Java § ∀x J(x) ○ Solution 2 § If U= every student § Let C(x)≔x is a student in the class § Let J(x)≔x has taken a course in Java § Let ∀x (C(x)→J(x)) • Some but not all students in this class has taken a course in Java. ○ Let C(x)≔x is a student in the class ○ Let J(x)≔x has taken a course in Java ○ Some but not all § ∃x J(x)∧¬∀x J(x) § ≡∃x J(x)∧ ∃x ¬J(x) ○ Solution § ∃x(C(x)∧J(x))∧¬∀x(C(x)→J(x)) § ≡∃x(C(x)∧J(x))∧¬∀x (C(x)→J(x)) § ≡∃x(C(x)∧J(x))∧∀x ¬(C(x)→J(x)) § ≡∃x(C(x)∧J(x))∧ ∃x (C(x)∧¬J(x)) Equivalences in Predicate Logic • Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value ○ for every predicate substituted into these statements and ○ for every domain of discourse used for the variables in the expressions. • The notation S≡T indicates that S and T are logically equivalent. • Example: ∀x ¬¬S(x) ≡ ∀x S(x) Negating Quantified Expressions • Consider ∀x J(x) ○ “Every student in your class has taken a course in Java.” ○ Here J(x) is “x has taken a course in Java” and ○ the domain is students in your class. ○ Negating the original statement gives “It is not the case that every student in your class has taken Java.” ○ This implies that “There is a student in your class who has not taken Java.” ○ Symbolically ¬∀x J(x) and ∃x ¬J(x) are equivalent • Consider ∃x J(x) ○ “There is a student in this class who has taken a course in Java.” ○ Where J(x) is “x has taken a course in Java.” ○ Negating the original statement gives “It is not the case that there is a student in this class who has taken Java.” ○ This implies that “Every student in this class has not taken Java” ○ Symbolically ¬∃x J(x) and ∀x ¬J(x) are equivalent Equivalent Statements • ∀x(P(x)∧Q(x))≡∀x P(x)∧∀x Q(x) • ∀x(P(x)∨Q(x))≠∀x P(x)∨∀x Q(x) ○ Let U=N={0,1,2,3…} ○ Let P(x)≔x is even ○ Let Q(x)≔x is odd ○ ∀x(P(x)∨Q(x)): every natural number is even or odd ○ ∀x P(x)∨∀x Q(x): every natural number is even or every natural number is odd • ∀x P(x)≡∀z P(z) Lewis Carroll Example • The first two are called premises and the third is called the conclusion. 1. “All lions are fierce.” 2. “Some lions do not drink coffee.” 3. “Some fierce creatures do not drink coffee.” • Define ○ U≔ all creatures ○ L(x)≔x is a lion ○ F(x)≔x is fierce ○ C(x)≔x drinks coffee • Translation ○ ∀x (L(x)→F(x)) ○ ∃x (L(x)∧¬C(x)) ○ ∃x(F(x)∧¬C(x)) Some Predicate Calculus Definitions • An assertion involving predicates and quantifiers is valid if it is true ○ for all domains ○ every propositional function substituted for the predicates in the assertion. • Example: ∀x ¬S(x)⟷¬∃x S(x) • An assertion involving predicates is satisfiable if it is true ○ for some domains ○ some propositional functions that can be substituted for the predicates in the assertion. • Otherwise it is unsatisfiable. • Example: ∀x (F(x)⟷T(x)) not valid but satisfiable • Example: ∀x(F(x)∧¬F(x)) unsatisfiable

Read More >>

1.3 Propositional Equivalences

Tautologies, Contradictions, and Contingencies • Tautology ○ A tautology is a proposition which is always true. ○ Example: p∨¬p • Contradiction ○ A contradiction is a proposition which is always false. ○ Example: p∧¬p • Contingency ○ A contingency is a proposition which is neither a tautology nor a contradiction ○ Example: p Logically Equivalent • Two compound propositions p and q are logically equivalent if p↔q is a tautology. • We write this as p⇔q or as p≡q where p and q are compound propositions. • Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree. • Example p q ¬p ¬p∨q p→q T T F T T T F F F F F T T T T F F T T T De Morgan’s Laws • ¬(p∧q)≡¬p∨¬q • ¬(p∨q)≡¬p∧¬q • Truth Table p q ¬p ¬q p∨q ¬(p∨q) ¬p∧¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T Key Logical Equivalences • Identity Laws ○ p∧T≡p ○ p∨F≡p • Domination Laws ○ p∨T≡T ○ p∧F≡F • Idempotent Laws ○ p∨p≡p ○ p∧p≡p • Double Negation Law ○ ¬(¬p)≡p • Negation Laws ○ p∨¬p≡T ○ p∧¬p≡F • Commutative Laws ○ p∧q≡q∧p ○ p∨q=q∨p • Associative Laws ○ (p∨q)∨r=p∨(q∨r) ○ (p∧q)∧r=p∧(q∧r) • Distributive Laws ○ p∨(q∧r)≡(p∨q)∧(p∨r) ○ p∧(q∨r)≡(p∧q)∨(p∧r) • Absorption Laws ○ p∨(p∧q)≡p ○ p∧(p∨q)≡p • Logical Equivalences Involving Conditional Statements ○ p→q≡¬p∨q ○ p→q≡¬q→¬p ○ p∨q≡¬p→q ○ p∧q≡¬(p→¬q) ○ ¬(p→q)≡p∧¬q ○ (p→q)∧(p→r)≡p→(q∧r) ○ (p→r)∧(q→r)≡(p∨q)→r ○ (p→q)∨(p→r)≡p→(q∨r) ○ (p→r)∨(q→r)≡(p∧q)→r • Logical Equivalences Involving Biconditional Statements ○ p⟷q≡(p→q)∧(q→p) ○ p⟷q≡¬p⟷¬q ○ p⟷q≡(p∧q)∨(¬p∧¬q) ○ ¬(p⟷q)≡p⟷¬q Constructing New Logical Equivalences • We can show that two expressions are logically equivalent by developing a series of logically equivalent statements. • To prove that A≡B we produce a series of equivalences beginning with A and ending with B. ○ A≡A_1≡A_2≡…≡A_n≡B • Keep in mind that whenever a proposition (represented by a propositional variable) occurs in the equivalences listed earlier, it may be replaced by an arbitrarily complex compound proposition. Propositional Satisfiability • A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. • When no such assignments exist, the compound proposition is unsatisfiable. • A compound proposition is unsatisfiable if and only if its negation is a tautology. Questions on Propositional Satisfiability • (p∨¬q)∧(q∨¬r)∧(r∨¬p) ○ p∨¬q=T⇒set p=T ○ q∨¬r=T⇒set q=T ○ r∨¬p=T⇒set r=T ○ One solution: p=q=r=T • (p∨¬q)∧(q∨¬r)∧(r∨¬p)∧(p∨q∨r)∧(¬p∨¬q∨¬r) ○ Not satisfiable. ○ Check each possible assignment of truth values to the propositional variables and none will make the proposition true. Notation • ⋁24_(j=1)^n▒p_j ≡p_1∨p_2∨…∨p_n • ⋀24_(j=1)^n▒p_j ≡p_1∧p_2∧…∧p_n Sudoku • A Sudoku puzzle is represented by a 9×9 grid made up of nine 3×3 subgrids, known as blocks. • Some of the 81 cells of the puzzle are assigned one of the numbers 1,2, …, 9. • The puzzle is solved by assigning numbers to each blank cell so that every row, column and block contains each of the nine possible numbers. • Example • Encoding as a Satisfiability Problem ○ Let p(i,j,n) denote the proposition that is true when the number n is in the cell in the ith row and the jth column. ○ There are 9×9×9 = 729 such propositions. ○ In the sample puzzle p(5,1,6) is true, but p(5,j,6) is false for j = 2,3,…, 9 ○ For each cell with a given value, assert p(i,j,n), when the cell in row i and column j has the given value. ○ Assert that every row contains every number. § ⋀24_(i=1)^9▒⋀24_(n=1)^9▒⋁24_(j=1)^9▒p(i,j,n) ○ Assert that every column contains every number. § ⋀24_(j=1)^9▒⋀24_(n=1)^9▒⋁24_(i=1)^9▒p(i,j,n) ○ Assert that each of the 3×3 blocks contain every number. § ⋀24_(r=0)^2▒⋀24_(s=0)^2▒⋀24_(n=1)^9▒⋀24_(i=1)^3▒⋁24_(j=1)^3▒p(3r+i,3s+j,n) ○ Assert that no cell contains more than one number. Take the conjunction over all values of n, n’, i, and j, where each variable ranges from 1 to 9 and n≠n′ of § p(i,j,n)→¬p(i,j,n′) • Solving Satisfiability Problems ○ To solve a Sudoku puzzle, we need to find an assignment of truth values to the 729 variables of the form p(i,j,n) that makes the conjunction of the assertions true. ○ Those variables that are assigned to yield a solution to the puzzle. ○ A truth table can always be used to determine the satisfiability of a compound proposition. ○ But this is too complex even for modern computers for large problems. ○ There has been much work on developing efficient methods for solving satisfiability problems as many practical problems can be translated into satisfiability problems.

Read More >>

1.2 Applications of Propositional Logic

Translating English Sentences • Steps to convert an English sentence to a statement in propositional logic ○ Identify atomic propositions and represent using propositional variables. ○ Determine appropriate logical connectives • Example: “If I go to Harry’s or to the country, I will not go shopping.” ○ p: "I go to Harry’s." ○ q: "I go to the country." ○ r: "I will go shopping." ○ p∨q→¬r • Example: “You can get an extra piece of pie if you have completed your homework or if you are extremely hungry” ○ p: You have completed your homework ○ q: You are extremely hungry ○ r: You can get an extra piece of pie ○ p∨q→r System Specifications • System and Software engineers take requirements in English and express them in a precise specification language based on logic. • Example: “The automated reply cannot be sent when the file system is full” ○ p: “The automated reply can be sent” ○ q: “The file system is full.” ○ q→¬ p Logic Puzzles • An island has two kinds of inhabitants, knights, who always tell the truth, and knaves, who always lie. • You go to the island and meet A and B. ○ A says “B is a knight.” ○ B says “The two of us are of opposite types.” • What are the types of A and B? ○ Let p and q be the statements that A is a knight and B is a knight, respectively. ○ So, then Øp represents the proposition that A is a knave and Øq that B is a knave. ○ If A is a knight, then p is true. Since knights tell the truth, q must also be true. Then (p ∧Øq)∨(Øp∧q) would have to be true, but it is not. So, A is not a knight and therefore Øp must be true. ○ If A is a knave, then B must not be a knight since knaves always lie. So, then both Øp and Øq hold since both are knaves. Logic Circuits • Electronic circuits; each input/output signal can be viewed as a 0 or 1. ○ 0 represents False ○ 1 represents True • Complicated circuits are constructed from three basic circuits called gates. ○ The inverter (NOT gate) takes an input bit and produces the negation of that bit. ○ The OR gate takes two input bits and produces the value equivalent to the disjunction of the two bits. ○ The AND gate takes two input bits and produces the value equivalent to the conjunction of the two bits. • More complicated digital circuits can be constructed by combining these basic circuits to produce the desired output given the input signals by building a circuit for each piece of the output expression and then combining them.

Read More >>