OLI - 3. Semantics

A _____ specifies a unique truth-value (either T or F) for each atomic formula.

• \n If φ is an atomic formula (sentential letter) of sentential logic, then φ is true on σ∗ just in case σ assigns the value T to φ, and false otherwise.

• If φ is a formula of the form ¬ψ, then φ is true on σ∗ just in case ψ is false on σ∗, and false otherwise.

• If φ is a formula of the form (ψ&ρ), then φ is true on σ∗ just in case both ψ and ρ are true on σ∗, and false otherwise.

• If φ is a formula of the form (ψ∨ρ), then φ is true on σ∗ just in case either ψ is true on σ∗ or ρ is true on σ∗, and false otherwise.

• If φ is a formula of the form (ψ→ρ), then φ is true on σ∗ just in case either ψ is false on σ∗ or ρ is true on σ∗, and false otherwise.

A formula is called logically true or a _____ just in case it is true on every truth-value assignment.

A formula is called a _____ just in case it is false on every truth-value assignment.

A formula is called a _____ just in case it is true on some truth-value assignments, and false on others.

The conclusion of an argument is a _____ of its premises if and only if any truth-value assignment that makes all the premises true also makes the conclusion true.

An argument is _____ if and only if its conclusion is a logical consequence of its premises.

An argument is _____ in case it is not valid, that is, if there is some truth-value assignment that makes the premises true, but the conclusion false.

A truth-value assignment that makes the premises of an argument true and its conclusion false is called a _____ to the argument.

The _____ of an argument with premises φ1,...,φn and conclusion χ is the formula ((φ1&(...&φn))→χ).

A branch of truth-tree is _____ if and only if it contains both any formula φ and the negation ¬φ of that formula.

A branch of truth-tree is _____ if and only if it is not closed.

A branch of truth-tree is _____ if no further decomposition rules can be applied on that branch. All closed branches are completed. An open branch is completed if every formula on the branch is either a literal or already decomposed.

A truth-tree is _____ if every branch of the tree is completed.

1. Start by writing down the formula for which you want to generate a truth-tree.

2. Based on the syntactic form of the expression, apply the appropriate truth-tree rule, putting a check mark next to the formula to indicate that it has been analyzed.

3. For each open branch, determine whether the branch contains both any formula φ and its negation ¬φ. If any branch does contain a formula and its negation, mark the branch closed. If all branches in the tree are closed, you are done. Otherwise, continue to the next step.

4. If the only formulae on open branches that do not have check marks next to them are atomic formulae or negations of atomic formulae, you are done. Otherwise, continue to the next step.

   1. Choose an unchecked formula on an open branch in the truth-tree that is not atomic and not the negation of an atomic formula, and apply this procedure to that formula, starting with step 2.