Propositional Logic: Semantics

Truth Values
Definition of Truth Values
Truth values are the fundamental building blocks of propositional logic. Each proposition can
have one of two truth values: True (T) or False (F).

• True (T): A statement is considered true if it accurately reflects reality.

• False (F): A statement is false if it does not reflect reality.

In propositional logic, each proposition is assigned a truth value that determines its truth status
within a logical framework. The significance of truth values lies in their role in evaluating
logical expressions and the relationships between propositions.

Evaluating Validity Using Truth Tables

Truth tables can be used to evaluate the validity of arguments. An argument is valid if, whenever
the premises are true, the conclusion is also true.

Example: Evaluate the argument:

• Premise 1: P→ Q

• Premise 2: Q→ R

• Conclusion: P→ R

Construct a truth table including all statements:

 P Q R P → Q Q → R P → R Validity

TT T T T T T

TT F T F F F

TF T F T T T

TF F F T F F

FT T T T T T

FT F T F T F

FF T T T T T

FF F T T T T

Interpretation: The argument is valid if there are no cases where the premises are true and the
conclusion is false.

Limitations of Truth Tables

While truth tables are powerful, they have limitations:

• Scalability: The number of rows grows exponentially with the number of

propositions. For n propositions, the truth table has 2^n rows.

• Complexity: Complex logical expressions may require extensive tables, making them
difficult to interpret.

Models and Logical Consequences

In propositional logic, understanding models and logical consequences is vital for interpreting
logical expressions and determining the truth of statements based on certain conditions. A
model is an assignment of truth values to propositions, and a logical consequence is a
conclusion that must be true if the premises are true.

Models in Propositional Logic

Definition of a Model
A model for a propositional logic statement consists of a specific assignment of truth values to
the propositional variables. Each unique combination of truth values represents a different
model.
Types of Models
1. Satisfying Model: A model that makes a given logical formula true.

2. Non-Satisfying Model: A model that makes the formula false.

Example: For the proposition P∨Q:

• Model 1: P=T,Q=F → Satisfying Model (True)

• Model 2: P=F,Q=F → Non-Satisfying Model (False)

Model Representation
A model can be represented as a vector where each element corresponds to a proposition.

Example: Let’s say we have propositions P,Q,R. The model (T,F,T) indicates:

• P is True

• Q is False

• R is True

Logical Consequences

Definition of Logical Consequence

A formula C is a logical consequence of a set of premises {P1,P2,...,Pn}if every model that
satisfies the premises also satisfies C.

Mathematically, this can be expressed as:

{P1,P2,...,Pn}⊨C

This means that in every model where all Pi are true, C must also be true.

Notation

The notation A⊢B indicates that B is derivable from A. If we can derive B from A using a set
of inference rules, we say A entails B.

Evaluating Logical Consequences Using Truth Tables

Truth tables can be used to evaluate logical consequences. To do this:

1. Construct the Truth Table for the premises and the conclusion.

2. Identify Satisfying Models: Look for rows in the table where all premises are true.

3. Check the Conclusion: If all those rows also make the conclusion true, then the
conclusion is a logical consequence of the premises.
Example: Evaluate if P→Q logically entails ¬P∨Q.

P Q P → Q ¬P ¬P ∨ Q

TT T F T

TF F F F

FT T T T

FF T T T

Interpretation: In rows where P→Q is true (rows 1, 3, 4), the conclusion ¬P∨Q is also true in
every case, confirming that P→Q logically entails ¬P∨Q.

Models and Interpretation

Understanding Interpretation
In propositional logic, an interpretation assigns meaning to each proposition. For example:

• Let P represent "It is raining."

• Let Q represent "The ground is wet."

Interpretation of P→Q: If it is raining, then the ground is wet.

Interpretation and Models

Different interpretations may yield different models. Each model provides a unique truth value
assignment, affecting the evaluation of logical expressions.

Example: Consider propositions in a scenario of a game:

• Let A represent "Player 1 wins."

• Let B represent "Player 2 wins."

Models would evaluate different outcomes based on player actions.

Validity and Soundness

Validity
An argument is valid if the conclusion follows logically from the premises. If it is possible for
the premises to be true while the conclusion is false, the argument is invalid.
Example of Valid Argument:

1. Premise: If it rains, the ground is wet. (P→Q)

2. Premise: It is raining. (P)

3. Conclusion: The ground is wet. (Q)

Soundness
An argument is sound if it is valid and all its premises are true. This guarantees that the
conclusion is also true.

Example:

• If both premises are factually correct and lead to a true conclusion, the argument is
sound.

Basic Logical Equivalences

Several fundamental logical equivalences are widely used in propositional logic. These
equivalences form the basis for simplifying and manipulating logical expressions.

Identity Law

• P∧True≡ P

• P∨False≡P

Domination Law

• P∧False≡False

• P∨True≡True

Idempotent Law

• P∧P≡P

• P∨P≡P

Complement Law

• P∧¬P≡False

• P∨¬P≡True

3.2.5 Double Negation Law

• ¬(¬P)≡P
De Morgan's Laws

• ¬(P∧Q)≡¬P∨¬Q

• ¬(P∨Q)≡¬P∧¬Q

Using Truth Tables to Verify Equivalences

Truth tables can be used to establish the equivalence between two logical expressions. To
demonstrate that P≡ Q:

1. Construct truth tables for both P and Q.

2. Compare the resulting truth values. If they match in all cases, P≡Q.

Example: Verify that ¬(P∧Q)≡¬P∨¬Q using a truth table.

P Q P ∧ Q ¬(P ∧ Q) ¬P ¬Q ¬P ∨ ¬Q

TT T F F F F

TF F T F T T

FT F T T F T

FF F T T T T

Conclusion: Since ¬(P∧Q) have the same truth values in all cases, they are logically equivalent.

Properties of Logical Equivalences

Understanding the properties of logical equivalences aids in simplifying logical expressions
and constructing arguments effectively. Here are key properties:

Reflexivity

• Every proposition is equivalent to itself: P≡P.

Symmetry

• If P≡ Q, then Q≡ P.

Transitivity

• If P≡Q and Q≡R, then P≡R.

Application of Logical Equivalences
Logical equivalences are extensively used in various domains, including computer science,
mathematics, and philosophy. They play a vital role in:

1. Simplifying Boolean Expressions: By applying logical equivalences, complex

Boolean expressions can be reduced to simpler forms, making them easier to analyze
and implement in algorithms.

2. Proving Arguments: Logical equivalences help establish the validity of arguments in

formal proofs. They allow us to transform premises into conclusions through
systematic manipulation.

Examples of Logical Equivalence Transformations

Let's explore some examples of transforming logical expressions using equivalences.

Example 1: Simplify (P∨(Q∧R))∧(P∨¬Q).

Step 1: Apply distribution:

• P∨(Q∧R)≡(P∨Q)∧(P∨R)

• New expression: ((P∨Q)∧(P∨R))∧(P∨¬Q)

Step 2: Use the associativity law:

• New expression: (P∨Q)∧((P∨R)∧(P∨¬Q))

Example 2: Show that P→Q≡¬P∨Q.

Step 1: Start with P→Q.

Step 2: Apply the definition of implication:

• P→Q≡¬P∨Q

Step 3: Verify using a truth table (as shown previously).