Propositional logic studies inferential relationships among sentences, focusing on logical operators called propositional connectives. Inferential relationships are the logical connections that enable one proposition’s truth to be derived from the truth of other propositions. In simpler terms, they are the logical links that establish how the truth of one proposition can imply the truth of another based on the rules of logic. These relationships are fundamental in deductive reasoning and the analysis of logical arguments. Propositional logic establishes how the truth values of propositions relate through logical operators, enabling automated reasoning processes and logical deductions in fields such as computer science, artificial intelligence, and formal verification.

Propositional Language

A propositional language \( \text{Prop}[P] \) consists of a set of atomic propositions, logical connectives and formation rules that define the syntax of the language.

  • Atomic proposition are indivisible units of the language, represented by symbols such as \( p, q, r \). A propositional language is defined as: \[\text{Prop}[P] \quad P = \lbrace p, q, r \rbrace \tag{1}\]

  • Logical connectives are: \( \neg \), \( \wedge \), \( \lor \), \( \rightarrow \), \( \leftrightarrow \), \( \oplus \).

  • Propositions that can be defined from the atomic formulas of the propositional language using logical connectives are called well-formed formulas (WFF).

These elements constitute the syntax of a propositional language.

Logical Connectives

Propositional connectives are logical operators used in propositional logic to combine or modify atomic propositions, determining the truth conditions of the resulting propositions. An atomic proposition is a statement that cannot be broken down into simpler parts (it is raining). The main propositional connectives are:

  • \(\neg\), negation: it inverts the truth value of a proposition. If a proposition \( p \) is true, the negation \(\neg p\) is false.

  • \(\wedge\), conjunction: represents AND. A conjunction \( p \wedge q \) is true only if both propositions ( p ) and ( q ) are true.

  • \(\lor\), disjunction: represents OR. A disjunction \( p \lor q \) is true if at least one of the propositions \( p \) or \( q \) is true.

  • \(\rightarrow\), implication: represents if…then. An implication \( p \rightarrow q \) is false only if \( p \) is true and \( q \) is false, that is, when the premises of the implication are true and the conclusion is false.

  • \(\leftrightarrow\), biconditional, represents if and only if. A biconditional \( p \leftrightarrow q \) is true if \( p \) and \( q \) have the same truth value, meaning both are true or both are false.

  • \(\oplus\), exclusive or (XOR): it is true if exactly one proposition is true.

Example

Suppose we have the propositional language with \(\text{Prop}[P]\) defined as follows:

\[Prop[P] \quad P = \lbrace p, q\rbrace \]

  • \(p =\) the door is open.
  • \(q =\) the window is open.

Let’s try to represent the following statements using the atomic formulas \( p \) and \( q \) and logical connectives:

  • The door closed \(\equiv \) The door is not open \[\neg p\]
  • The door and the window are open \[ p \wedge q \]
  • If the door is open, then the window is open \[ p \rightarrow q \]
  • The door is open if and only if the window is open \[ p \leftrightarrow q \]
  • Either the door is open or the window is open, but not both \[ p \oplus q \]
  • It is not the case that if the door is open, then the window is open \[ \neg (p \rightarrow q) \]

Formation rules

Formation rules define how atomic propositions and logical connectives can be combined to form well-formed formulas (WFFs).

  • If \( p \) is an atomic proposition, then \( p \) is a WFF.
  • If \( p \) is a WFF, then \( \neg p \) is a WFF.
  • If \( p \) and \( q \) are WFFs, then \( p \wedge q \), \( p \lor q \), \( p \rightarrow q \), \( p \leftrightarrow q \), and \( p \oplus q \) are WFFs.

Semantic

The meaning of the syntactically correct expressions of \(\text{Prop}[P]\) is provided by semantics. Defining the propositional language’s interpretation domain is crucial to defining the language’s semantics. This domain comprises the set of objects that denote the possible meanings of the language’s expressions. The interpretation domain of propositional logic consists of the set of Boolean values (true, false):

\[\text{Bool} = {T, F} \tag{2}\]

Given two formulas \( p \) and \( q \), the truth table illustrating their relationships using propositional connectives is as follows:

\begin{array}{cc|cccccc} p & q & \neg p & p \wedge q & p \lor q & p \rightarrow q & p \leftrightarrow q & p \oplus q \\ \hline T & T & F & T & T & T & T & F \\ T & F & F & F & T & F & F & T \\ F & T & T & F & T & T & F & T \\ F & F & T & F & F & T & T & F \\ \tag{3} \end{array}

The provided truth table offers a comprehensive analysis of the behavior of key propositional connectives. By examining all possible truth value combinations for propositions \( p \) and \( q \), the transformative impact of each connective on these values becomes evident.

Note that:

  • An implication can be rewritten in disjunctive form, that is, as a disjunction of literals, as \( p \rightarrow q \equiv \neg p \lor q \).

  • A biconditional can be rewritten in disjunctive form, that is, as a disjunction of literals, as: \( p \leftrightarrow q \equiv (\neg p \lor q) \land (\neg q \lor p) \).

  • The symbol \(\equiv\) represents the logical equivalence.

Interpretations

An interpretation \( M \) of \( p \) is defined as a function such that:

\[ M:p \rightarrow \lbrace Bool \rbrace \tag{4}\]

  • If \( p \) is a formula and \( M \) an interpretation of \( p \), the notation \( M \models p \) indicates that \( p \) is true in \( M \) and \( M \) is said to be a model of \( p \).

  • If \( p \) is a formula and \( M \) an interpretation of \( p \), the notation \( M \not\models p \) indicates that \( p \) is false in \( M \) and \( M \) is said to be a counter-model of \( p \).

Suppose we have the following atomic formulas:

  • \( p =\) the door is open.
  • \( q =\) the window is open.

Consider the interpretation \( M \) where \( p \) is true and \( q \) is false. We want to verify if \( M \) satisfies the formula \( p \rightarrow \neg q \). In this case we have:

\begin{array}{c c|c c} p & q & \neg q & p \rightarrow \neg q \\ \hline T & F & T & T \\ \tag{5} \end{array}

In this interpretation M, \( p \) is true, \( q \) is false \( \neg q \) is true. Since \( p \) is true and \( \neg q \) is true, the implication \( p \rightarrow \neg q \) is true. Therefore, \( M \models p \rightarrow \neg q \).

  • A formula \( p \) is inconsistent if there is no interpretation \( M \) such that \( M \models p \). In other words, \( p\) is false under all possible interpretations. \[\forall M, M \not\models p \]

  • A formula \( p \) is satisfiable if there exists at least one interpretation \( M \) such that \( M \models p \). In other words, \( p \) is true under at least one interpretation. \[ \exists M, M \models p \]

  • A formula \( p \) is a tautology if \( p \) is true under all possible interpretations. In other words, for every interpretation \( M \), \( M \models p\). \[\forall M, M \models p\]

Logical Consequence

A formula \( p \) is said to be a logical consequence of a set of formulas \( S \) if and only if every interpretation \( M \) that satisfies all formulas in \( S\) also satisfies \( p \). \[ S \models p \] In other words, \( p \) is a logical consequence of \( S \) if \( p \) must be true whenever all the formulas in \( S \) are true.

Suppose we have:

  • \( S = \lbrace A,A \rightarrow B \rbrace \)
  • \( p = B \)

We want to verify if \( p \) is a logical consequence of \( S \). To verify it let’s create a truth table:

\begin{array}{c c|c} A & B & A \rightarrow B \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \end{array}

When both formulas \( A \) and \( A \rightarrow B \) are true, \( B \) must also be true. Therefore, we can conclude that \(S \models B \) demonstrating that \( B \) is a logical consequence of \( S \).

Automated deduction systems offer algorithms that enable automatic reasoning to solve problems related to determining logical consequences. The concept of logical consequence is essential not only in formal logic language but also in AI models. It ensures the validity of arguments, the correctness of reasoning, and the reliability of conclusions derived from premises. This, in turn, ensures that AI systems can make correct and consistent decisions based on formalized knowledge.