A synthetic access controller has three inputs. A means the request is approved, B means the badge is valid, and O means a supervisor override is active. Its written requirement is: Grant access exactly when the request is approved and at least one of badge validity or override holds. An override replaces the badge requirement; it does not replace approval.
Translate this into F=A∧(B∨O). The symbol ∧ means AND, so both its operands must be true. The symbol ∨ means inclusive OR: either operand or both may be true. “Exactly when” states both directions: every accepted input should meet the requirement, and every input meeting the requirement should be accepted. This is a teaching model, not a real authorization system.
A colleague proposes G=(A∧B)∨O. Test A=0, B=0, O=1 before looking at the whole table. F is false because approval is absent; G is true because its final OR accepts any override. The difference is the scope of the parentheses, not a typographical preference. This single input is a counterexample to equivalence.
Predict
At A=B=O=1 both formulas are true. Does this successful test repair the counterexample? No: equivalence requires agreement on every input, so a disagreement elsewhere remains decisive.
A total assignment gives every declared variable a truth value. A formula is satisfiable if at least one total assignment makes it true; such an assignment is a witness. It is valid if every total assignment makes it true. It is unsatisfiable if none makes it true. Valid formulas are satisfiable because this finite Boolean domain has assignments, but satisfiable formulas need not be valid.
Predict the three counts for our example: how many rows make F true, how many make G true, and how many make them disagree? Distinguish these counts before deciding whether either formula is “correct.” Correctness relative to a specification is a claim about the required behavior, not simply a high number of true rows.
Experiment
Construct the intermediate columns first. Computing B∨O and A∧B separately exposes exactly where the candidate changes the requirement. Here 0 denotes false and 1 denotes true. Row order is A, then B, then O, with O changing fastest.
A
B
O
B∨O
A∧B
F=A∧(B∨O)
G=(A∧B)∨O
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
1
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
0
0
1
0
1
1
0
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
F has three satisfying assignments, G has five, and the formulas disagree twice. Both are satisfiable; neither is valid. The complete table proves these statements because all eight assignments to the three independent Boolean inputs appear, not because eight is a large sample.
Use the approval comparison below. Set only O true and predict the outputs before selecting Reveal finite certificate. Then set A true as well and explain why agreement on this new row does not establish equivalence. Try the pair of contradictions next: can two formulas be equivalent even when neither has a satisfying assignment? Finally, compare an implication with its converse and identify a disagreeing row. These are fixed formula comparisons; the tool is not an editor for arbitrary specifications.
Find a witness, then check every assignment
Choose a fixed pair of formulas. A, B and O are independent Boolean inputs in this table; unchecked means false. Predict both outputs for your selected assignment, then predict whether one matching row proves equivalence.
Left: A ∧ (B ∨ O). Right: (A ∧ B) ∨ O. The symbols ∧, ∨, ¬ and → mean AND, inclusive OR, NOT and material implication.
No result revealed. Changing the example or an input clears the certificate.
Temporary practice; no saved answer or mastery credit. The tool compares only the displayed fixed formulas.
Understand
The kind of claim determines the evidence needed. To prove satisfiability, exhibit one complete assignment and verify evaluation. To refute validity, exhibit one false row. To prove validity or unsatisfiability by a table, account for every assignment. For a large formula, a general argument may be clearer than writing all rows.
Equivalence of formulas F and G means their values agree for every assignment. The formula F↔G expresses agreement on one assignment; saying it is valid expresses agreement on all assignments. Thus equivalence is not the same as both formulas being true. Two contradictions, such as p∧¬p and q∧¬q, are equivalent because both are always false.
There is another useful certificate. A disagreement occurs precisely when (F∧¬G)∨(¬F∧G) is true. Therefore F and G are equivalent exactly when this disagreement formula is unsatisfiable. This follows in both directions: any satisfying assignment to it separates the outputs, and any separating assignment satisfies one of its two terms.
Entailment introduces assumptions. Premises Γ entail a conclusion C when every assignment making all premises true also makes C true. For example, premises p→q and p entail q. If both premises hold, p is true and the implication forces q. A counterexample to entailment would have to make every premise true while making the conclusion false. A row violating a premise is not such a counterexample.
The implication p→q means ¬p∨q. It is true whenever p is false, regardless of q. This material implication does not express causation or a chronological guarantee. In particular, p→q alone does not entail q: p=0,q=0 satisfies the premise but not the proposed conclusion.
Premises are consistent if they have a common satisfying assignment. If premises include p and ¬p, no assignment satisfies them all. They then entail every conclusion in classical propositional semantics, because no counterexample can satisfy all the premises. This vacuity supplies no model and establishes no fact about a real system. Check consistency separately rather than treating an impossible specification as a successful design.
For n distinct Boolean variables there are 2^n total assignments: each variable independently has two choices. A finite formula can be evaluated recursively on each assignment, giving an always-terminating satisfiability procedure. When n=0, there is one empty assignment, not zero assignments. This proves decidability for finite propositional formulas, not practical efficiency for arbitrary sizes, and not termination of arbitrary programs described elsewhere in the curriculum.
A truth table becomes a probability calculation only after weighting
Suppose an output requires input A together with at least one of B or C. Its formula is F=(A∧B)∨(A∧C), equivalent by distributivity to A∧(B∨C). Exactly three of the eight assignments make F true. That does not usually make its probability3/8: counting true rows equally assumes all eight assignments have equal probability.
Same logic, different probability
Predict the output probability of (A AND B) OR (A AND C). Change the B/C coupling while keeping their marginal probabilities fixed. A remains independent of the entire pair (B,C) in every case.
P(B AND C)=8/36. Output probability: 84/216. The three true assignments are unchanged; their weights need not be equal.
A
B
C
A AND B
A AND C
Output
Probability
0
0
0
0
0
0
24/216
0
0
1
0
0
0
48/216
0
1
0
0
0
0
12/216
0
1
1
0
0
0
24/216
1
0
0
0
0
0
24/216
1
0
1
0
1
1
48/216
1
1
0
1
0
1
12/216
1
1
1
1
1
1
24/216
All eight weights sum to216/216, including zero-probability rows. Boolean equivalence is independent of these weights; equal event probabilities alone do not prove equivalence. This exact synthetic distribution is temporary exploration, not a measured reliability claim or automatic mastery.
For mutually independent Boolean inputs with true probabilities p, q and r, an assignment’s weight is the product of its three true/false probabilities. For example the assignment (1,1,0) has weight p·q·(1−r). The three disjoint true rows (1,1,0), (1,0,1) and (1,1,1) therefore give p q(1−r)+p(1−q)r+p q r = p(q+r−qr). With p=1/2, q=1/3 and r=2/3, their weights are1/18,2/9 and1/9; their sum is7/18. The equal-row answer3/8 is different.
There is another trap: the two events A∧B and A∧C share A. Even under mutually independent input bits, those two events are generally dependent. Their intersection is A∧B∧C, with probability pqr, whereas multiplying their separate probabilities gives p²qr. Inclusion-exclusion requires the actual intersection, not an unsupported product. At the default probabilities, using that product would incorrectly produce4/9 instead of7/18.
Hold the marginals fixed and change the joint law
Keep A independent of the pair (B,C), but no longer assume B and C independent. Write t=P(B∧C). The four pair weights for (B,C)=(1,1), (1,0), (0,1), (0,0) are t, q−t, r−t and1−q−r+t. Nonnegativity is equivalent to max(0,q+r−1)≤t≤min(q,r); these weights also sum to one and recover the stated marginals. Conversely every t in that interval defines a valid pair distribution, so this is a complete feasibility condition, not just a bound.
The output probability is now p(q+r−t). At the same marginals1/2,1/3,2/3, maximal overlap t=1/3 gives1/3, independent overlap t=2/9 gives7/18, and minimal overlap t=0 gives1/2. The truth function has not changed, but its distribution has. Knowing the marginals alone does not identify the output probability. Without independence of A from the pair, even this formula needs additional joint information; individual pairwise independence is not being substituted for that hypothesis.
Logical equivalence means agreement on every assignment and therefore equal probabilities under every distribution. Equal probabilities under one distribution are weaker: two distinct events can have the same total weight, and disagreement on zero-probability rows is invisible to that particular probability calculation. Keep a logical certificate separate from a probabilistic assumption audit.
Apply
Change the access rule: an override may bypass approval, but a valid badge is always required. Write your formula before checking the answer. The revised formula is H=B∧(A∨O). At A=0,B=1,O=1 it grants access; at A=1,B=0,O=1 it refuses. Those two contrasting rows distinguish the new interpretation from the original F. Explain the requirement in words as well as symbols so that a reviewer can check the translation.
Now suppose an environmental contract guarantees O→A: whenever override is active, approval is also present. Under this contract the original F and flawed G agree. If O=1, A must be one and both formulas are true. If O=0, both reduce to A∧B. These exhaustive cases prove agreement for every allowed assignment. The previously discovered disagreements violate the contract.
This does not make the formulas globally equivalent. If an input fault permits O=1,A=0, the distinction returns. A conditional certificate should say that (O→A)→(F↔G) is valid, preserving the assumption explicitly. Do not silently remove disallowed rows and then advertise unconditional correctness.
As optional depth, the full table also gives a direct formula from accepted rows. F is equivalent to (A∧¬B∧O)∨(A∧B∧¬O)∨(A∧B∧O): each term singles out one accepted assignment. This construction can be checked row by row, but the original factored requirement is shorter and easier to explain. More symbols do not automatically give a stronger certificate.
Continue
In the written tasks, choose whether you need one witness, one counterexample, an exhaustive table, or a proof covering arbitrary assignments. Keep separate claims separate: a consistent premise set, a valid inference and a specification matching its intended meaning are not interchangeable achievements.
For a concrete recap of AND, OR and material implication, return to the logic, sets and implication investigation. Its finite universe illustrates truth conditions; this lesson’s Boolean table instead enumerates all assignments to declared independent variables. A finite sample of situations proves a global claim only when those situations exhaust the stated domain.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
For mutually independent Boolean inputs with probabilities P(A)=p,P(B)=q,P(C)=r, compute the probability of F=(A∧B)∨(A∧C) by disjoint weighted truth-table rows. Evaluate at p=1/2,q=1/3,r=2/3. Explain both the equal-row-count error and the error of treating A∧B and A∧C as independent.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Keep A independent of (B,C), with marginal true probabilities p,q,r, but allow B,C to be dependent. Characterize every feasible t=P(B∧C), construct its four joint weights and derive P((A∧B)∨(A∧C)). At p=1/2,q=1/3,r=2/3, give the exact range of output probabilities.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
In a synthetic controller, p means the primary sensor is selected, q means the backup sensor is selected, and r means maintenance is active. The output must be true exactly when one sensor is selected and maintenance is inactive. Construct a Boolean formula, give all eight rows with intermediate columns for “at least one” and “both”, and list its satisfying assignments. Repair the candidate (p∨q)∧¬r and explain why one successful test cannot certify the repair.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For variables p and q, classify F=(p→q), G=(p∧(p→q))→q, and H=(p↔q)∧(p↔¬q) as valid, satisfiable but not valid, or unsatisfiable. Supply the appropriate witness, counterexample or all-assignments proof for each. Explain why “the program returned true once” cannot establish any of the universal claims.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Let F=(p∨q)∧(¬p∨r) and G=(¬p∧q)∨(p∧r). Prove F and G equivalent by splitting on p, including both possible truth values of p. Then refute equivalence of F with the shortened candidate K=p∧r. Explain why finding an assignment making both F and K true is insufficient.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Consider premises Γ={p→q, q→r, p}. Prove Γ entails r and exhibit a model of Γ. Remove the premise p and decide whether the conclusion still follows. Then add ¬r to the original Γ: prove the new set inconsistent, explain whether it entails an unrelated variable s in classical propositional semantics, and show that deleting any one of its four premises restores consistency.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A device assumes C=p∨q. Two proposed output rules are F=p→q and G=q. Decide whether F and G are globally equivalent and whether they are equivalent under C. Give a global counterexample if needed. State one validity test and one unsatisfiability test that certify equivalence under C. Explain what changes if the device can enter p=q=0.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For F=(p∨q)∧(¬p∨r), a search routine has fixed p=0 but left q,r unassigned. Is this a satisfying assignment, a partial assignment with some satisfying completion, or a partial assignment whose every completion satisfies F? Enumerate its four completions. Repeat for the partial assignment p=0,q=1. Finally describe an always-terminating exhaustive satisfiability procedure for an arbitrary finite formula with n distinct variables; explain what its worst-case 2^n assignment count does and does not establish.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
