OLI - 3. Semantics

Truth-Value Assignment

Truth-Value Assignment

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

Characteristic Truth-table for Conjunction

Characteristic Truth-table for Disjunction

Characteristic Truth-table for the Conditional

Characteristic Truth-table for Negation

Truth and Falsity Relative to a Truth-Value Assignment

• \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.

Tautology

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

Contradictory Formula

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

Contingent Formula

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

Logical Consequence

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.

Validity

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

Invalidity

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.

Counterexample

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

Conditional Analogue

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

Truth-Tree Construction Rules

Truth-Tree: Closed Branch

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

Truth-Tree: Open Branch

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

Truth-Tree: Completed Branch

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.

Completed Truth-Tree

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

Procedure for Generating Truth-Trees

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.

Truth-values

Truth-functional

Function

Truth-tables

Truth-conditions

Characteristic truth-table

Logically true

Logical consequence

Contradictory

Truth-trees