Contingency & Satisfiable

Tautology Contradiction Contingency

• Propositions are declarative statements that are either true or false but not both.
• Connectives are used to combine propositions (for example ∧, ∨, →, ↔, ∼).

Determining the Nature of a Compound Proposition

Typically you are given a compound proposition and asked to determine whether it is a tautology, contradiction or contingency. The usual methods are:

• Construct a truth table and inspect the final column.
• Simplify the proposition using propositional algebra (identities, De Morgan, distributive, etc.).
• Interpret the proposition using Boolean algebra or digital-logic notation (useful for quick reasoning).

Definitions and Relationships

Tautology

• A compound proposition is a tautology if and only if it is true for all possible truth assignments to its propositional variables.
• In a truth table the last column contains only T (True).

Contradiction

• A compound proposition is a contradiction if and only if it is false for all possible truth assignments to its propositional variables.
• In a truth table the last column contains only F (False).

Contingency

• A compound proposition is a contingency if and only if it is neither a tautology nor a contradiction.
• In a truth table the last column contains both T and F.

Valid and Invalid

• A compound proposition is called valid precisely when it is a tautology.
• A compound proposition is called invalid when it is not a tautology (it may be a contradiction or a contingency).

Falsifiable and Unfalsifiable

• A compound proposition is falsifiable if there exists some assignment of truth values that makes it false.
• A compound proposition is unfalsifiable if it can never be made false (i.e., it is a tautology).

Satisfiable and Unsatisfiable

• A compound proposition is satisfiable if there exists some assignment of truth values that makes it true.
• A compound proposition is unsatisfiable if it cannot be made true under any assignment (i.e., it is a contradiction).

Important relationships (summary)

• All contradictions are invalid, falsifiable and unsatisfiable.
• All contingencies are invalid, falsifiable and satisfiable.
• All tautologies are valid, unfalsifiable and satisfiable.
• Not every satisfiable proposition is a tautology.

Example : Determine the nature of following propositions-

Example : Determine the nature of following propositions-

1. p ∧ ∼p
2. (p ∧ (p → q)) → ∼q
3. [ (p → q) ∧ (q → r) ] ∧ ( p ∧ ∼r)
4. ∼(p → q) ∨ (∼p ∨ (p ∧ q))
5. (p ↔ r) → (∼q → (p ∧ r))

Solution:

We solve each part by one or more methods: truth table, propositional algebra and (where helpful) digital-logic interpretation.

Part 1: p ∧ ∼p

Method-1: Using Truth Table

The last column of the truth table contains only F.

• Contradiction
• Invalid
• Falsifiable
• Unsatisfiable

Method-2: Using Algebra of Propositions

The proposition is

p ∧ ∼p

By the complement law

p ∧ ∼p = F

Thus the proposition is a contradiction, invalid, falsifiable and unsatisfiable.

Method-3: Using Digital Electronics

Interpret p as a Boolean variable; p' denotes ∼p.

The expression becomes p.p'.

p.p' = 0

Therefore it is a contradiction, invalid, falsifiable and unsatisfiable.

Part 2: (p ∧ (p → q)) → ∼q

Method-01: Using Truth Table

The last column contains both T and F.

• Contingency
• Invalid
• Falsifiable
• Satisfiable

Method-02: Using Algebra of Propositions

Start with the proposition

(p ∧ (p → q)) → ∼q

Replace implication by its equivalent

p → q = ∼p ∨ q

Hence

(p ∧ (∼p ∨ q)) → ∼q

Use implication identity: A → B ≡ ∼A ∨ B

So

∼(p ∧ (∼p ∨ q)) ∨ ∼q

Distribute inside the negation

∼((p ∧ ∼p) ∨ (p ∧ q)) ∨ ∼q

Use complement law p ∧ ∼p = F

So

∼(F ∨ (p ∧ q)) ∨ ∼q

Identity law gives

∼(p ∧ q) ∨ ∼q

Apply De Morgan to ∼(p ∧ q)

∼p ∨ ∼q ∨ ∼q

Simplify duplicate ∼q

∼p ∨ ∼q

The result is neither universally true nor universally false.

Therefore it is a contingency, invalid, falsifiable and satisfiable.

Method-03: Using Digital Electronics

Translate to Boolean symbols: p' for ∼p and q' for ∼q.

The expression becomes

(p.(p' + q))' + q'

Expand p.(p' + q) = p.p' + p.q

Since p.p' = 0, this simplifies to p.q

So we have (p.q)' + q'

Apply De Morgan: (p.q)' = p' + q'

Thus

p' + q' + q'

Simplify duplicate q'

p' + q'

Not identically 0 or 1, hence contingency, invalid, falsifiable and satisfiable.

Part 3: [ (p → q) ∧ (q → r) ] ∧ ( p ∧ ∼r)

Method-01: Using Truth Table

Let R denote the expression.

The last column contains only F.

• Contradiction
• Invalid
• Falsifiable
• Unsatisfiable

Method-02: Using Algebra of Propositions

Start with

[ (p → q) ∧ (q → r) ] ∧ ( p ∧ ∼r)

Replace implications: p → q = ∼p ∨ q and q → r = ∼q ∨ r

So

[ (∼p ∨ q) ∧ (∼q ∨ r) ] ∧ ( p ∧ ∼r)

Distribute to combine the first two terms

[ ((∼p ∨ q) ∧ ∼q) ∨ ((∼p ∨ q) ∧ r) ] ∧ ( p ∧ ∼r)

Distribute within each bracket

[ ((∼p ∧ ∼q) ∨ (q ∧ ∼q)) ∨ ((∼p ∧ r) ∨ (q ∧ r)) ] ∧ ( p ∧ ∼r)

Use q ∧ ∼q = F

[ (∼p ∧ ∼q) ∨ (∼p ∧ r) ∨ (q ∧ r) ] ∧ ( p ∧ ∼r)

Distribute across the conjunction with (p ∧ ∼r)

((∼p ∧ ∼q) ∧ ( p ∧ ∼r)) ∨ ((∼p ∧ r) ∧ ( p ∧ ∼r)) ∨ ((q ∧ r) ∧ ( p ∧ ∼r))

Each clause contains a pair of complementary literals (for example ∼p ∧ p or r ∧ ∼r)

Thus each clause simplifies to F

F ∨ F ∨ F = F

Therefore the whole expression is F (contradiction), hence invalid, falsifiable and unsatisfiable.

Method-03: Using Digital Electronics

Replace variables by Boolean symbols and implications similarly.

The expression becomes

[ (p' + q).(q' + r) ] . (p.r')

Expand the product: (p' + q).(q' + r) = p'.q' + p'.r + q.q' + q.r

Since q.q' = 0 this is p'.q' + p'.r + q.r

Multiply by (p.r')

p'.q'.p.r' + p'.r.p.r' + q.r.p.r'

Each product contains complementary pairs (for example p' and p, or r and r')

Each term simplifies to 0

Sum is 0

Thus the expression is 0 (contradiction), so invalid, falsifiable and unsatisfiable.

Part 4: ∼(p → q) ∨ (∼p ∨ (p ∧ q))

Method-01: Using Truth Table

Let R denote the expression.

The last column contains only T.

• Tautology
• Valid
• Unfalsifiable
• Satisfiable

Method-02: Using Algebra of Propositions

Start with

∼(p → q) ∨ (∼p ∨ (p ∧ q))

Replace implication p → q by ∼p ∨ q

So

∼(∼p ∨ q) ∨ (∼p ∨ (p ∧ q))

Apply De Morgan to the first term

(p ∧ ∼q) ∨ (∼p ∨ (p ∧ q))

Use distributive law on the second part: ∼p ∨ (p ∧ q) = (∼p ∨ p) ∧ (∼p ∨ q)

Thus

(p ∧ ∼q) ∨ ( (∼p ∨ p) ∧ (∼p ∨ q) )

Since (∼p ∨ p) = T, simplify

(p ∧ ∼q) ∨ (∼p ∨ q)

Rearrange using associativity

((p ∧ ∼q) ∨ ∼p) ∨ q

Distribute inside the first bracket

((p ∨ ∼p) ∧ (∼q ∨ ∼p)) ∨ q

(T ∧ (∼q ∨ ∼p)) ∨ q

(∼q ∨ ∼p) ∨ q

Rearrange

∼p ∨ (q ∨ ∼q)

q ∨ ∼q = T

So ∼p ∨ T = T

Hence the expression is identically T.

Therefore it is a tautology, valid, unfalsifiable and satisfiable.

Method-03: Using Digital Electronics

Use Boolean notation: p' for ∼p and q' for ∼q.

The expression becomes

(p' + q)' + (p' + p.q)

Use the transposition theorem or distributive expansions to simplify the second term

(p' + p.q) = (p' + p).(p' + q) = 1.(p' + q) = p' + q

So the whole expression is

(p' + q)' + (p' + q)

By Boolean identity A' + A = 1

Therefore the expression equals 1

Hence it is a tautology, valid, unfalsifiable and satisfiable.

Part 5: (p ↔ r) → (∼q → (p ∧ r))

Method-01: Using Truth Table

Let R denote the expression.

The last column contains both T and F.

• Contingency
• Invalid
• Falsifiable
• Satisfiable

Method-02: Using Algebra of Propositions

Start with

(p ↔ r) → (∼q → (p ∧ r))

Rewrite the right implication: ∼q → (p ∧ r) = q ∨ (p ∧ r)

Thus the expression becomes

(p ↔ r) → (q ∨ (p ∧ r))

Apply implication identity: A → B ≡ ∼A ∨ B

So

∼(p ↔ r) ∨ q ∨ (p ∧ r)

Replace biconditional p ↔ r by (p → r) ∧ (r → p)

Thus ∼((p → r) ∧ (r → p)) ∨ q ∨ (p ∧ r)

Replace implications inside

∼((∼p ∨ r) ∧ (∼r ∨ p)) ∨ q ∨ (p ∧ r)

Distribute to simplify the inner conjunction

∼[ ((∼p ∨ r) ∧ ∼r) ∨ ((∼p ∨ r) ∧ p) ] ∨ q ∨ (p ∧ r)

Distribute within each part and eliminate contradictions such as r ∧ ∼r or p ∧ ∼p

After simplification the inside becomes (∼p ∧ ∼r) ∨ (r ∧ p)

Apply De Morgan to the negation

∼(∼p ∧ ∼r) ∧ ∼(r ∧ p)

Which is

(p ∨ r) ∧ (∼r ∨ ∼p)

Distribute this with the remaining disjunction q ∨ (p ∧ r)

Carry out distributive and identity simplifications

Reduce to

(p ∧ ∼r) ∨ q ∨ (∼p ∧ r) ∨ (p ∧ r)

Group terms and simplify using (∼p ∨ p) = T

Finally this reduces to

p ∨ q ∨ r

The result is neither identically T nor identically F under all assignments.

Therefore the given proposition is a contingency, invalid, falsifiable and satisfiable.

Method-03: Using Digital Electronics

Translate the biconditional and implications and apply De Morgan where needed.

One convenient simplification leads to

p'.r + r'.p + q + p.r

Group terms where possible

(p' + p).r + r'.p + q

Which yields

r + r'.p + q

Further simplification leads to

p + q + r

Therefore expression is neither 0 nor 1 for all assignments and is a contingency, invalid, falsifiable and satisfiable.

Concluding Remarks

To identify the nature of a compound proposition use truth tables for certainty, algebraic simplification for compact proofs, and Boolean/digital-logic interpretation for intuition and quick checks. Keep the standard equivalences at hand: De Morgan, distributive, associative, identity and complement laws, and the translation p → q ≡ ∼p ∨ q and p ↔ q ≡ (p → q) ∧ (q → p).

Summary of key tests:

• Truth table last column all T → tautology (valid, unfalsifiable, satisfiable).
• Truth table last column all F → contradiction (invalid, falsifiable, unsatisfiable).
• Truth table last column mixed T and F → contingency (invalid, falsifiable, satisfiable).