4. The Logic of Boolean Connectives

THE LOGIC OF BOOLEAN CONNECTIVES

TAUTOLOGIES AND LOGICAL TRUTHS

  • Definition of Tautologies:

    • A tautology is a logical statement that is true in every possible interpretation or assignment of truth values to its atomic components.

    • It owes its truth solely to the meanings of the truth-functional connectives involved and does not depend on the specific atomic sentences it contains.

  • Definition of Logical Truths:

    • A logical truth is a statement that is true in all logically possible circumstances.

    • Example: The statement a=a is logically true because it cannot be false.

  • Definition of Tarski's World Necessities:

    • These are true in every world we can create within Tarski's World, which is a model designed for exploring logical truths.

  • Relationships:

    • Tautologies and logical truths are subsets of Tarski's World necessities.

    • Every tautology is a Tarski’s World necessity, but not every Tarski’s World necessity is a tautology.

TRUTH-FUNCTIONALITY AND LOGICAL POSSIBILITY

  • Not all logical connectives are truth-functional.

    • Example: The belief that Carson City is the capital of Nevada does not determine whether John believes it because belief is not strictly based on truth-functional values.

  • Distinction between necessary true statements and contingent truths:

    • Example: a=a is necessarily true while other truths may not hold in all possible worlds.

TRUTH-FUNCTIONAL CONNECTIVES

  • Truth-functional connectives include:

    • Conjunction (P ∧ Q)

    • Disjunction (P ∨ Q)

    • Negation (¬P)

  • Truth-functionality allows the construction of truth tables to analyze the logic behind the connectives:

    • It leads to conclusions about logical consequences, logical equivalences, and logical truths.

LOGICAL TRUTH

  • A sentence is a logical truth if it is a logical consequence of every set of sentences.

    • A logical consequence is true in every circumstance where its premises are true.

    • Logical truths are necessarily true and are logical consequences of no premises at all.

LOGICAL NECESSITY

  • A logically true sentence is true in all logically possible situations.

    • Example: The sentence a=a cannot be false.

  • Example of a statement that is true but not a logical truth:

    • The statement about traveling faster than light, which is true due to physical constraints, not logical necessity.

TARSKE'S WORLD SENTENCES

  • All worlds created within Tarski's World must be logically possible circumstances.

    • A sentence that can be made true by blocks in Tarski’s World exemplifies logical possibility.

  • Tarski's World Necessary Sentences:

    • They are true across all Tarski's World situations.

    • While some sentences may be Tarski's World necessaries, they do not have to be logically necessary.

RELATIONS OF NECESSITIES

  • Tarski's World necessities that are not logical truths exist.

    • Example: The statement Tet(a) ∨ Cube(a) ∨ Dodec(a) is true in Tarski’s World but not logically necessary.

  • Tarski's World possibilities assert a broader realm of possibilities than true logical necessity.

TAUTOLOGY TESTING WITH TRUTH TABLES

  • Constructing a truth table can determine whether a formula is a tautology.

    • A formula is a tautology if it is true across all rows.

    • The number of rows in a truth table is determined by the number of atomic sentences, specifically 2^n, where n is the number of atomic sentences.

  • Each row’s outcome helps establish if the entire formula is true or false and indicates whether the sentence is logically sound.

LOGICAL EQUIVALENCE AND TAUTOLOGICAL EQUIVALENCE

  • Two sentences are logically equivalent if they share the same truth values across all logical contexts.

  • Tautological Equivalence is stricter than logical equivalence; all tautologically equivalent sentences are logically equivalent, but not vice versa.

LOGICAL AND TAUTOLOGICAL CONSEQUENCES

  • Tautological consequence is a specific type of logical consequence.

  • It can be established using truth tables to validate that S is true wherever premises hold true.

  • The limits of truth tables being fully mechanistic can yield possibilities not captured by logical structures.

PUSHING NEGATION AROUND

  • Techniques include substituting logical equivalents to move negation within formulas.

  • The principle of double negation allows for simplification such that the truth value remains unchanged during transformations.

  • A formula can typically be rewritten to have negations applied only to atomic sentences, achieving a normalized form.

NORMAL FORMS

  • Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF) are expressional forms aimed at standardizing logical statements.

    • CNF: A conjunction of disjunctions.

    • DNF: A disjunction of conjunctions.

  • Procedures exist to test if a formula is in CNF or DNF based on strict criteria related to the placement of logical operators and negations.

DISTRIBUTION LAWS

  • The distribution of conjunction over disjunction and vice versa are analogous to algebraic principles of distribution.

    • Example equivalences include the commutativity and associativity of both conjunction and disjunction.

  • Simplification steps are laid out for transforming statements of mixed connectives into standardized forms.

  • This procedural transformation securely elucidates logical structures confirming their truth-preserving dynamics leading consistently to CNF and DNF.

EXAMPLES AND PROCEDURES

  • Various examples of applying the principles described including checking normal forms, the use of truth tables, and the operational logic of connectives.

  • Each case is systematically evaluated to adhere to truth conditions that govern logical statements.

CONCLUSIONS

  • Overall, the study of logical truths, tautologies, and the operations surrounding them fosters a clearer understanding of logic and reasoning within both philosophical and computational paradigms.