---
title: "Tableau for a formula set"
subject: "Discrete Structure"
chapter: 1
key: "semester_4/discrete_structure:tableau-formula-set"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/tableau-formula-set
site: BCT Engineering
---

# Tableau for a formula set

Discrete Structure · Chapter 1: Logic, Induction and Reasoning

- Asked in: 2069 Bhadra, 6 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/tableau-formula-set
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-1

## Question

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.

## 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.

## Answer

Φ = { (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**
1. p ∧ t is an α-formula, so add p and t.
2. (p ∧ ¬q) → s is a β-formula, so split into ¬(p ∧ ¬q) | s.
3. On the left, ¬(p ∧ ¬q) is a β-formula, so split into ¬p | q. The branch with ¬p contains p, so it closes (×).
4. On the branch with q, expand ¬q ∨ ¬r into ¬q | ¬r. The ¬q branch contains q, so it closes (×); the ¬r branch stays open.
5. On the right branch (s), expand ¬q ∨ ¬r into ¬q | ¬r. Both stay open.

#### Tableau
```text
 {(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).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How is a formula set Φ placed in the tableau?
   A. Each formula on its own tree
   B. All formulas on one branch, since all must be true
   C. Only the first formula
   D. As a disjunction
   Answer: B. A model must satisfy all formulas, so they share a branch. (Key point: Set on one branch)

2. Why does the branch ¬p close?
   A. It also contains p (from p ∧ t)
   B. It has no literals
   C. It contains s
   D. It contains ¬q
   Answer: A. p ∧ t added p, so ¬p and p are complementary. (Key point: Closing branch)

3. Why does the branch q, ¬q close?
   A. ¬q ∨ ¬r splits and ¬q contradicts q
   B. Because s is present
   C. Because t is present
   D. Because r is false
   Answer: A. On the q branch, ¬q conflicts with q. (Key point: Closing second)

4. How many open branches does the tableau have, and what does that mean?
   A. Three; Φ is satisfiable
   B. Five; Φ is valid
   C. Two; Φ is unsatisfiable
   D. Zero; Φ is unsatisfiable
   Answer: A. Two of five branches close, three stay open, so the set is satisfiable. (Key point: Result)

## Close variants set in other exams

- [Tableau for (p∧¬q)→s](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atableau-p-and-not-q-implies-s) — Discrete Structure, chapter 1, asked 5×
- [Tableau for ¬((p∧q)∨r)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atableau-not-pq-or-r) — Discrete Structure, chapter 1, asked 5×
- [Tableau for (T∨S)→¬Q](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atableau-t-or-s-implies-not-q) — Discrete Structure, chapter 1, asked 5×

## Related in other subjects

- [Discrete and continuous random variables](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Adiscrete-continuous-rv-mean-variance) — Probability and Statistics, chapter 2