Logic & Its Applications

Goal: Construct the truth table for the compound proposition $p \oplus (p \lor q)$ and simplify the resulting expression.

Step-by-Step Evaluation:

1. Identify Variables: There are two variables ($p$ and $q$), which requires $2^2 = 4$ rows to cover all truth assignments.
2. Evaluate $p \lor q$ (Conjunction): $p \lor q$ is true in all rows except when both $p$ and $q$ are false.
3. Evaluate $p \oplus (p \lor q)$ (Exclusive OR): The exclusive OR operation $\oplus$ evaluates to true if and only if its two operands have different truth values.

Conclusion: Looking at the final column, the output is true only when $p$ is false ($F$) and $q$ is true ($T$). Therefore, the compound proposition is logically equivalent to $\lnot p \land q$. ∎

Goal: Translate the English statement into a formal propositional logic statement using the variables provided.

Step-by-Step Translation:

1. Analyze the Connective: The statement uses the conditional construct "only if". Recall that the proposition "$p \text{ only if } q$" translates to $p \to q$. The condition following "only if" represents a necessary condition and forms the consequent (on the right of the arrow).
2. Identify Necessary Condition: "you are a faculty member and have a valid ID" is the necessary condition. This is translated as a conjunction: $(F \land I)$.
3. Identify Antecedent: "You can borrow the rare book" is the antecedent: $B$.
4. Formulate Implication: Combining these yields: $$B \to (F \land I)$$

Common Pitfall Note: Avoid writing $(F \land I) \to B$. This represents the converse ("if you are a faculty member and have a valid ID, you can borrow the book"), which is not implied by the original statement. ∎

Goal: Determine which of the four given compound propositions is not a tautology by finding a counterexample (a truth assignment that makes the statement false).

Analysis of Options:

• Option (a): This is the Law of Hypothetical Syllogism. It states that implication is transitive, which is a fundamental tautology.
• Option (c): The antecedent is $a \land b \land c$. If this conjunction is true, then both $a$ and $c$ must be true. Therefore, the consequent $c \lor a$ must also be true. This implication is always true, so it is a tautology.
• Option (d): The expression is equivalent to $\lnot a \lor (\lnot b \lor a) \equiv (\lnot a \lor a) \lor \lnot b \equiv T \lor \lnot b \equiv T$. Since it simplifies to $T$, it is a tautology.
• Option (b): Let's test for a truth assignment that makes this implication false ($T \to F = F$):
  1. To make the consequent $(\lnot b \to (a \land c))$ false, we must have $\lnot b = T$ (meaning $b = F$) and $a \land c = F$.
  2. To make the antecedent $(a \leftrightarrow c)$ true, $a$ and $c$ must share the same truth value.
  3. Since $a \land c = F$ and they must have the same value, we set $a = F$ and $c = F$.
  4. Substitute $a=F, b=F, c=F$ into the full expression: $$\text{Antecedent: } F \leftrightarrow F \equiv T$$ $$\text{Consequent: } \lnot F \to (F \land F) \equiv T \to F \equiv F$$ $$\text{Implication: } T \to F \equiv F$$

Conclusion: The truth assignment $a = F, b = F, c = F$ makes option (b) false. Thus, (b) is not a tautology. Answer: (b). ∎

Goal: Determine if there exists at least one truth assignment to the variables $p$ and $q$ that makes the compound proposition true.

Step-by-Step Analysis:

1. Simplify individual clauses using implication-to-disjunction equivalence ($a \to b \equiv \lnot a \lor b$):
   • $C_1: p \to q \equiv \lnot p \lor q$
   • $C_2: p \to \lnot q \equiv \lnot p \lor \lnot q$
   • $C_3: \lnot p \to q \equiv p \lor q$
   • $C_4: \lnot p \to \lnot q \equiv p \lor \lnot q$
2. Evaluate cases for assignment of variable $p$:
   • Case 1 ($p = T$): Under this assignment, the first two clauses reduce: $$C_1 \land C_2 \equiv (F \lor q) \land (F \lor \lnot q) \equiv q \land \lnot q \equiv F$$ Since the conjunction contains a contradiction ($F$), the entire statement is false for $p = T$.
   • Case 2 ($p = F$): Under this assignment, the last two clauses reduce: $$C_3 \land C_4 \equiv (F \lor q) \land (F \lor \lnot q) \equiv q \land \lnot q \equiv F$$ Similarly, this evaluates to false for $p = F$.

Conclusion: No assignment of truth values to $p$ and $q$ can satisfy the compound proposition. Therefore, the expression is unsatisfiable (a contradiction). ∎

Goal: Prove that a compound proposition $\varphi$ is unsatisfiable if and only if its negation $\lnot\varphi$ is a tautology.

Proof:

1. Part 1: Negation of an unsatisfiable proposition is a tautology.
   • Assume $\varphi$ is unsatisfiable. By definition, under any truth assignment $v$, the valuation of $\varphi$ is false: $$v(\varphi) = F \quad \text{for all assignments } v.$$
   • By definition of the negation operator, we evaluate the negation $\lnot\varphi$: $$v(\lnot\varphi) = \lnot(v(\varphi)) = \lnot(F) = T \quad \text{for all assignments } v.$$
   • Since $v(\lnot\varphi) = T$ for every possible truth assignment, $\lnot\varphi$ is a tautology.
2. Part 2: Negation of a tautology is unsatisfiable.
   • Assume $\varphi$ is a tautology. By definition, under any truth assignment $v$, the valuation of $\varphi$ is true: $$v(\varphi) = T \quad \text{for all assignments } v.$$
   • Evaluating the negation $\lnot\varphi$: $$v(\lnot\varphi) = \lnot(v(\varphi)) = \lnot(T) = F \quad \text{for all assignments } v.$$
   • Since $v(\lnot\varphi) = F$ for every possible truth assignment, $\lnot\varphi$ is unsatisfiable. ∎

Goal: Translate the arithmetic expression `(x * (1 - y)) + ((1 - x) * y)` over binary variables $x, y \in \{0, 1\}$ into standard propositional logic operators.

Step-by-Step Translation:

1. Translate multiplication and subtraction:
   • In binary arithmetic, multiplication represents the logical AND ($\land$) operation: $a \cdot b = 1 \iff a=1 \land b=1$.
   • The term $(1 - z)$ represents the logical NOT ($\lnot$) operation: $1 - z = 1 \iff z = 0$.
2. Evaluate the two terms:
   • Term 1: $x \cdot (1 - y) \equiv x \land \lnot y$.
   • Term 2: $(1 - x) \cdot y \equiv \lnot x \land y$.
3. Translate addition:
   • Addition of these two binary terms yields: $(x \land \lnot y) + (\lnot x \land y)$.
   • Since the two terms cannot both be 1 simultaneously (as $x$ cannot be both 0 and 1), the sum is either 0 or 1. Thus, addition behaves as a logical disjunction ($\lor$) or exclusive-OR ($\oplus$).
4. Combine terms: $$ (x \land \lnot y) \lor (\lnot x \land y) $$

Conclusion: The expression evaluates to 1 when exactly one of $x$ or $y$ is 1. Therefore, it translates to the logical exclusive-OR: $x \oplus y$. ∎

Goal: Write a boolean expression over the bits $x_3, x_2, x_1, x_0$ that evaluates to true if and only if the integer $x$ represented by the bits is a multiple of 5.

Step-by-Step Analysis:

1. Identify multiples of 5: In the range $\{0, \ldots, 15\}$, the multiples of 5 are:
   • $0 = 0000_2$ (bits: $x_3=0, x_2=0, x_1=0, x_0=0$)
   • $5 = 0101_2$ (bits: $x_3=0, x_2=1, x_1=0, x_0=1$)
   • $10 = 1010_2$ (bits: $x_3=1, x_2=0, x_1=1, x_0=0$)
   • $15 = 1111_2$ (bits: $x_3=1, x_2=1, x_1=1, x_0=1$)
2. Identify patterns in bits:
   • In all four numbers, compare $x_3$ and $x_1$: they are always equal ($0=0$, $0=0$, $1=1$, $1=1$). This can be written as $(x_3 \leftrightarrow x_1)$.
   • Compare $x_2$ and $x_0$: they are also always equal ($0=0$, $1=1$, $0=0$, $1=1$). This can be written as $(x_2 \leftrightarrow x_0)$.

Conclusion: The boolean expression asserting divisibility of $x$ by 5 is: $$\text{Div}_5(x) = (x_3 \leftrightarrow x_1) \land (x_2 \leftrightarrow x_0)$$ To prove this holds for no other numbers, we can verify that any of the other 12 numbers fails this condition (e.g. $1 = 0001_2$ has $x_2=0, x_0=1$, which fails). ∎

Goal: Translate the given English sentence into a formal predicate logic expression using the provided predicates.

Step-by-Step Translation:

1. Identify the Subject ("Some students"): This indicates an existential quantifier over the students: $$\exists x \, (S(x) \land \dots)$$ We use $\land$ because we are asserting both that $x$ is a student, and that $x$ satisfies the rest of the property.
2. Translate the Property ("have never been asked a question by a faculty member"):
   • "For all faculty members $y$, $y$ has not asked $x$ a question."
   • This is formalized as: $\forall y \, (F(y) \to \lnot A(y, x))$. We use $\to$ here because the condition "never asked" applies only if $y$ is actually a faculty member.
3. Combine Quantifiers: $$\exists x \, (S(x) \land \forall y \, (F(y) \to \lnot A(y, x)))$$
4. Alternative formulation: We can also write "there does not exist a faculty member who asked $x$ a question": $$\exists x \, (S(x) \land \lnot \exists y \, (F(y) \land A(y, x)))$$ Both are logically equivalent. ∎

Goal: Formalize the English statement, apply the negation operator using quantifier laws, and translate the negated statement back into natural English.

Step-by-Step Derivation:

1. Formalize the original statement: Let $S(x)$ = "$x$ is a student in this class," $C(y)$ = "$y$ is a mathematics course offered at this school," and $T(x,y)$ = "$x$ has taken $y$." $$\varphi = \exists x \, (S(x) \land \forall y \, (C(y) \to T(x, y)))$$
2. Apply Negation: $$\lnot \varphi = \lnot \exists x \, (S(x) \land \forall y \, (C(y) \to T(x, y)))$$ Apply the quantifier negation rule ($\lnot \exists \equiv \forall \lnot$): $$\equiv \forall x \, \lnot (S(x) \land \forall y \, (C(y) \to T(x, y)))$$ Apply De Morgan's Law to the conjunction: $$\equiv \forall x \, (\lnot S(x) \lor \lnot \forall y \, (C(y) \to T(x, y)))$$ Apply quantifier negation ($\lnot \forall \equiv \exists \lnot$): $$\equiv \forall x \, (\lnot S(x) \lor \exists y \, \lnot (C(y) \to T(x, y)))$$ Recall that $\lnot(a \to b) \equiv a \land \lnot b$: $$\equiv \forall x \, (\lnot S(x) \lor \exists y \, (C(y) \land \lnot T(x, y)))$$ Rewrite disjunction back to conditional ($a \to b \equiv \lnot a \lor b$): $$\equiv \forall x \, (S(x) \to \exists y \, (C(y) \land \lnot T(x, y)))$$
3. Translate back to English: "For every student in this class, there is some mathematics course offered at this school that they have not taken." ∎

Goal: Negate Suresh's statement formally and select the matching English sentence.

Step-by-Step Negation:

1. Formalize Suresh's statement: Let $r$ denote a region, $t$ denote a town in region $r$ ($t \in r$), $i$ denote an inhabitant of town $t$ ($i \in t$), and $H(i)$ mean "$i$ is happy." $$\varphi = \forall r \, \exists t \in r \, \forall i \in t \, H(i)$$
2. Negate the formal statement step-by-step: $$\lnot\varphi = \lnot \left[ \forall r \, \exists t \in r \, \forall i \in t \, H(i) \right]$$ $$\equiv \exists r \, \lnot \left[ \exists t \in r \, \forall i \in t \, H(i) \right]$$ $$\equiv \exists r \, \forall t \in r \, \lnot \left[ \forall i \in t \, H(i) \right]$$ $$\equiv \exists r \, \forall t \in r \, \exists i \in t \, \lnot H(i)$$
3. Translate the result back to English: "There is a region ($\exists r$) where, in all towns in that region ($\forall t \in r$), there is at least one inhabitant who is unhappy ($\exists i \in t \, \lnot H(i)$)."

Conclusion: This matches option (d). ∎

Goal: Translate each English premise and the conclusion into predicate logic statements over the domain of all birds.

Step-by-Step Translation:

• (a) All hummingbirds are richly colored. "For all birds $x$, if $x$ is a hummingbird, then $x$ is richly colored." $$\forall x \, (P(x) \to S(x))$$
• (b) No large birds live on honey. "For all birds $x$, if $x$ is large, then $x$ does not live on honey." $$\forall x \, (Q(x) \to \lnot R(x))$$
• (c) Birds that do not live on honey are dull in color. "For all birds $x$, if $x$ does not live on honey, then $x$ is not richly colored (dull)." $$\forall x \, (\lnot R(x) \to \lnot S(x))$$ (Note: Contrapositively, this is equivalent to $\forall x \, (S(x) \to R(x))$).
• (d) Hummingbirds are small. (conclusion) "Small" means "not large". "For all birds $x$, if $x$ is a hummingbird, then $x$ is not large." $$\forall x \, (P(x) \to \lnot Q(x))$$ ∎

Goal: Expand the Boolean function $F(x,y,z) = (x+z)y$ into its canonical Sum-of-Products (SOP) form, where each term (minterm) contains all three variables.

Step-by-Step Algebraic Expansion:

1. Apply the distributive law: $$F = (x+z)y = xy + yz$$
2. Expand $xy$ to include $z$: Multiply by $(z + \bar{z})$ (since $z + \bar{z} = 1$): $$xy = xy(z + \bar{z}) = xyz + xy\bar{z}$$
3. Expand $yz$ to include $x$: Multiply by $(x + \bar{x})$: $$yz = yz(x + \bar{x}) = xyz + \bar{x}yz$$
4. Combine terms (OR them together) and remove duplicates: $$F = (xyz + xy\bar{z}) + (xyz + \bar{x}yz)$$ $$F = xyz + xy\bar{z} + \bar{x}yz$$

Conclusion: The canonical sum-of-products expansion is: $$F = xyz + xy\bar{z} + \bar{x}yz$$ ∎

Goal: Simplify the 2-variable Boolean expression $F = xy + x\bar y + \bar x y + \bar x \bar y$ using a Karnaugh Map.

Step-by-Step Minimization:

1. Draw and fill the 2-variable K-map:
   

   	$y=0$ ($\bar{y}$)	$y=1$ ($y$)
   $x=0$ ($\bar{x}$)	1 ($\bar x \bar y$)	1 ($\bar x y$)
   $x=1$ ($x$)	1 ($x \bar y$)	1 ($xy$)

2. Identify Groups: All 4 cells contain 1s. We can group all 4 cells into a single rectangular block of size $2^2 = 4$.
3. Determine Simplified Term: A group of size 4 in a 2-variable K-map covers the entire grid. Since all variables change state across the group, they are all eliminated.

Conclusion: The minimal SOP is: $$F = 1$$ This indicates the function is a tautology (always evaluates to 1). ∎

Goal: Find the minimal Sum-of-Products (SOP) form for the Boolean function $f(x,y,z)$ using a 3-variable K-map.

Step-by-Step Minimization:

1. Set up Gray Code grid columns for $yz$: Columns are ordered as $00, 01, 11, 10$.
2. Plot the minterms on the grid:

   	$yz=00$	$yz=01$	$yz=11$	$yz=10$
   $x=0$	1 ($\bar x\bar y\bar z$)	0	1 ($\bar x y z$)	0
   $x=1$	0	1 ($x\bar y z$)	0	1 ($xy\bar z$)

3. Attempt Grouping:
   • Notice that the 1s are arranged in a "checkerboard" pattern.
   • Recall that adjacent cells include wrap-around (leftmost and rightmost columns). Even considering wrap-around, no two 1s share an edge.
   • Hence, we cannot form any groups of size 2 or larger. Each minterm must remain isolated in a group of size 1.

Conclusion: No algebraic simplification is possible. The minimal SOP is the original four-term expression: $$f(x,y,z) = xy\bar z + x\bar y z + \bar x y z + \bar x \bar y \bar z$$ (Note: In terms of standard logic gates, this represents the 3-input exclusive-OR operation: $f = x \oplus y \oplus z$). ∎

Goal: Formulate the constraints of a 4×4 Sudoku puzzle as Well-Formed Formulas (WFFs) using the defined predicate $p(i,j,k)$.

Formulations:

• (a) Rule 1 (Rows): Every row $i$ must contain every digit $k$ (at least once), and no digit $k$ can appear in two different columns $j$ and $j'$ of row $i$: $$\bigwedge_{i=1}^{4}\bigwedge_{k=1}^{4}\left[\left(\bigvee_{j=1}^{4} p(i,j,k)\right) \land \bigwedge_{j \neq j'} \lnot(p(i,j,k) \land p(i,j',k))\right]$$
• (b) Rule 2 (Columns): Every column $j$ must contain every digit $k$, and no digit $k$ can appear in two different rows $i$ and $i'$ of column $j$: $$\bigwedge_{j=1}^{4}\bigwedge_{k=1}^{4}\left[\left(\bigvee_{i=1}^{4} p(i,j,k)\right) \land \bigwedge_{i \neq i'} \lnot(p(i,j,k) \land p(i',j,k))\right]$$
• (c) Rule 3 (2×2 subgrids): There are four subgrids, indexed by $(a,b) \in \{0,1\} \times \{0,1\}$, where subgrid $(a,b)$ covers rows $\{2a+1, 2a+2\}$ and columns $\{2b+1, 2b+2\}$. For each subgrid and each digit $k$, $k$ must appear: $$\bigwedge_{a=0}^{1}\bigwedge_{b=0}^{1}\bigwedge_{k=1}^{4}\left[ \left(\bigvee_{i=2a+1}^{2a+2}\bigvee_{j=2b+1}^{2b+2} p(i,j,k)\right) \land \bigwedge_{(i,j) \neq (i',j')} \lnot\big(p(i,j,k) \land p(i',j',k)\big) \right]$$ where the second conjunction is over distinct pairs of cells $(i,j)$ and $(i',j')$ in the same subgrid.
• (d) No cell has more than one number: For any cell $(i,j)$, if it contains $k$, it cannot contain any other digit $k'$: $$\bigwedge_{i=1}^{4}\bigwedge_{j=1}^{4}\bigwedge_{k \neq k'} \lnot(p(i,j,k) \land p(i,j,k'))$$ ∎

Goal: Prove the logical equivalence $\lnot(p \to q) \equiv p \land \lnot q$ step-by-step, citing the logical law used in each transition.

Proof:

Hence, the equivalence is proved. ∎

Goal: Describe the mapping of a 4×4 Sudoku puzzle into a propositional satisfiability (SAT) framework.

SAT Model Formulation:

1. Variables: We introduce $4 \times 4 \times 4 = 64$ binary variables. Define $p(i, j, k) = T$ if cell $(i, j)$ contains the digit $k \in \{1, 2, 3, 4\}$, and $F$ otherwise.
2. Constraints (expressed in Conjunctive Model Form, CNF):
   • Cell-Fill Constraint: Every cell $(i,j)$ must contain at least one digit: $$\bigwedge_{i=1}^4 \bigwedge_{j=1}^4 \left(p(i,j,1) \lor p(i,j,2) \lor p(i,j,3) \lor p(i,j,4)\right)$$
   • Cell-Uniqueness Constraint: A cell $(i,j)$ cannot contain more than one digit: $$\bigwedge_{i,j}\bigwedge_{k \neq k'} \left(\lnot p(i,j,k) \lor \lnot p(i,j,k')\right)$$
   • Row Constraints: Each row $i$ must contain each digit $k$ at least once: $$\bigwedge_{i=1}^4 \bigwedge_{k=1}^4 \left( \bigvee_{j=1}^4 p(i,j,k) \right)$$
   • Column Constraints: Each column $j$ must contain each digit $k$ at least once: $$\bigwedge_{j=1}^4 \bigwedge_{k=1}^4 \left( \bigvee_{i=1}^4 p(i,j,k) \right)$$
   • Subgrid Constraints: Each of the four 2×2 subgrids must contain each digit $k$: $$\bigwedge_{\text{grid } B}\bigwedge_{k=1}^4 \left( \bigvee_{(i,j) \in B} p(i,j,k) \right)$$
   • Givens (Hints): For any pre-filled cell $(i, j)$ with a known value $K$, add the unit clause clause: $$(p(i, j, K))$$
3. Solving: The conjunction of all these clauses forms a CNF formula. A SAT solver is run on this formula. The puzzle is solvable if and only if the formula is satisfiable, and any satisfying truth assignment directly corresponds to a valid solved Sudoku grid. ∎

Goal: Analyze the compound proposition $(p \to q) \land (\lnot q \to \lnot p)$ to determine if it is a tautology, and explain the correct mathematical context.

Analysis:

1. Apply the Contrapositive Law: Recall that an implication is logically equivalent to its contrapositive: $$\lnot q \to \lnot p \equiv p \to q$$
2. Substitute back into the expression: $$(p \to q) \land (\lnot q \to \lnot p) \equiv (p \to q) \land (p \to q)$$
3. Apply the Idempotent Law ($a \land a \equiv a$): $$\equiv p \to q$$
4. Evaluate truth value: The proposition simplifies to $p \to q$, which is false when $p = T$ and $q = F$. Since it is not true for all assignments, the expression is a contingency, not a tautology.

Correct Formulation Note: The question likely intended to ask about the biconditional statement rather than the conjunction: $$(p \to q) \leftrightarrow (\lnot q \to \lnot p)$$ Since $p \to q \equiv \lnot q \to \lnot p$, the biconditional $A \leftrightarrow B$ between two equivalent statements is indeed a tautology (always evaluates to true). ∎