Advanced Logic

Once we have the rules of deduction, we must ask ourselves about the power and reliability of the system itself. This is the domain of Meta-logic.

Soundness and Completeness

• Soundness: A logic system is sound if everything that can be proved is actually true. If you can derive $Q$ from $P$, then $P \implies Q$ is a tautology.
• Completeness: A logic system is complete if everything that is true can be proved. If $P \implies Q$ is a tautology, there exists a sequence of steps to derive $Q$ from $P$.

Propositional logic is both sound and complete. This means the “mechanical” process of manipulation perfectly matches the “semantic” truth of the universe.

Model Theory

Model theory studies the relationship between formal languages and their interpretations. A Model is a mathematical structure that makes the statements of a theory true.

If a set of statements has at least one model, it is Satisfiable. If it is true in all models, it is Valid.

Let’s use Python to check if a simple set of constraints is satisfiable (the SAT problem).

# A primitive SAT Solver
# We want to find A, B such that:
# (A OR B) AND (NOT A OR B) AND (A OR NOT B)

def check_constraints(A, B):
  c1 = A or B
  c2 = (not A) or B
  c3 = A or (not B)
  return c1 and c2 and c3

# Brute force all possibilities
possibilities = [(False, False), (False, True), (True, False), (True, True)]
solutions = [p for p in possibilities if check_constraints(p[0], p[1])]

print(f"Combinations: {possibilities}")
print(f"Valid Solutions (A, B): {solutions}")

In computer science, solving this efficiently ($P$ vs $NP$) is one of the most important open questions in mathematics.

Exercises