Definition of a model?

Question

computer science student here. I have problems finding a (satisfying (ha, jokes on me)) definition of a model ?

What would you call $\phi$ ? ( For me : it's a set of formulas, but i guess it has a name )

My main question is :

1. What is a model ?
2. Why is the example a model ?
3. Sentence 2 : (From one implicant, one can derive ...) suggests that $a \Lambda c \Lambda \neg d$ is a model, right ?

Answer 1

See Resolution: the set $\phi$ of formulas can be read as a single formula in Conjunctive normal form, i.e. as

$(a \lor b) \land (a \lor c) \land (\lnot d \lor \lnot e \lor \lnot f)$.

An implicant is a formula $\psi$ such that $\psi$ (logically) implies $\phi$, i.e. such that $\phi$ takes the value T whenever $\psi$ evaluates to T.

Thus, $a \land \lnot d, a \land \lnot e, a \land \lnot f, b \land c \land \lnot d, \ldots$ are all implicants of $\phi$.

A prime implicant is an "irreducible" implicant.

Consider e.g. $a \land \lnot d$: if we delete one of the two literals, the resulting formula does not implies $\phi$ any more.

The implicant $a \land c \land \lnot d$ instead, is not prime: we can remove the literal $c$ and what we get (i.e. $a \land \lnot d$) is still an implicant.

---

The usual way to semantically "evaluate" propositional formulas is through a truth assignment (or valuation) $v$, i.e. a function that assign a truth-value (T or F) to every sentential letter occurring in the formula.

The truth-value of the complete formula can then be computed with the truth tables for the connectives.

We say that a valuation $v$ satisfy a formula $\phi$ is the result of the above computation is T, i.e. if $v(\phi)=$ T.

We may look at $v$ as a row in the truth table for $\phi$ that assign T to it.

If we pick up the sentential letters that occur in the said row (i.e. those sentential letters tho which $v$ assign T), they form a model for $\phi$.

Thus, we have that $\{ a, c, \lnot d \}$ is a model for $\phi$.

The formula resulting from conjoining the literals of a model of a formula $\phi$ is an implicant of $\phi$.

Answer 2

In the context of propositional logic (which is what you have here), a model of a set of sentences $\phi$ is a truth-value assignment to each of the atomic variables involved in $\phi$ such that all statements in $\phi$ evaluate to True.

So in your example, they set $a,b,c,d,e$ all to True, and $f$ to False.

It is a model since with this assignment, all sentences in $\phi$ are true:

$a \lor b = True \lor True = True$

$a \lor c = True \lor True = True$

$\neg d \lor \neg e \lor \neg f = \neg True \lor \neg True \lor \neg False = False \lor False \lor True = True$