- Asked 5/9
- 2069 Bhadra · 6 marks
Tableau for a formula set
Short answer
Start with all formulas; from p∧t get p, t. Branch on (p∧¬q)→s: left gives ¬p (closed) or q, where ¬q∨¬r gives ¬q (closed) or ¬r (open); right branch with s gives open ¬q or ¬r. The set is satisfiable, e.g., p=t=q=T, r=F.
Draw the tableau for the formula set Φ = {(p∧¬q)→s, ¬q∨¬r, p∧t}, where ¬ denotes the negation of a variable, ∨ denotes the disjunction of variables, ∧ denotes the conjunction of variables and → denotes the implication.
Φ = { (p ∧ ¬q) → s, ¬q ∨ ¬r, p ∧ t }. All formulas of the set are placed on one branch, and a model must make all of them true.
Steps
- p ∧ t is an α-formula, so add p and t.
- (p ∧ ¬q) → s is a β-formula, so split into ¬(p ∧ ¬q) | s.
- On the left, ¬(p ∧ ¬q) is a β-formula, so split into ¬p | q. The branch with ¬p contains p, so it closes (×).
- On the branch with q, expand ¬q ∨ ¬r into ¬q | ¬r. The ¬q branch contains q, so it closes (×); the ¬r branch stays open.
- On the right branch (s), expand ¬q ∨ ¬r into ¬q | ¬r. Both stay open.
Tableau
{(p∧¬q)→s, ¬q∨¬r, p∧t}
p, t
/ \
¬(p∧¬q) s
/ \ / \
¬p q ¬q ¬r
× / \ o o
¬q ¬r
× o
Branch summary
| Branch | Literals | Status |
|---|---|---|
| 1 | p, t, ¬p | closed |
| 2 | p, t, q, ¬q | closed |
| 3 | p, t, q, ¬r | open |
| 4 | p, t, s, ¬q | open |
| 5 | p, t, s, ¬r | open |
Three branches are open, so the set Φ is satisfiable. Example models: p = t = q = T, r = F (s arbitrary); p = t = s = T, q = F (r arbitrary); p = t = s = T, r = F (q arbitrary).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Tableau for (p∧¬q)→s · Discrete Structure, chapter 1 · asked 5×
- Tableau for ¬((p∧q)∨r) · Discrete Structure, chapter 1 · asked 5×
- Tableau for (T∨S)→¬Q · Discrete Structure, chapter 1 · asked 5×
- Discrete and continuous random variables · Probability and Statistics, chapter 2