Formal Logic-Connectives, Truth Tables, Syntax, Semantics, Tautology, Validity, Well-Formed-Formula

Formal logic:

Connectives:

A logical connective is generally understood as a symbol or a word that connects two or more sentences. The sentences can be either a natural language or a formal language. The main motive of a logical connective is to connect the sentences in such a way that it presents the compound language in a grammatically valid way. The most common logical connectives are binary connectives that join two sentences which can be thought of as the function's operands. In addition, negation is considered to be a unary connective.

The various English words and word pairs that express logical connectives and they are:

• AND → '∧' (conjunction)
• OR → '∨' (disjunction)
• NOT → '¬' (negation)
• if then → '→' (implication)
• if and only if → '↔' (biconditional).

CNF: It stands for Conjunctive Normal Form. In a compound statement if two sentences are joined by using AND then it is called CNF.

DNF: It stands for Disjunctive Normal Form. In a compound statement if two sentences are joined by using OR then it is called DNF.

Truth Tables:

It is a table which gives all the outputs for all possible input. Given below is a truth table which represents the outputs for all possible inputs showing the relation between P and Q through disjunction, negation, implication.

Propositional Logic Syntax

The logical constants are True and False. The propositional symbols are P, Q, etc. which represents specific facts about the world.

• If S is a sentence, then (S) is a sentence.
• If S and R are sentenced then so are:
  S ∧ R: conjunction, S, and R are conjuncts.
  S ∨ R: disjunction, S, and R are disjuncts.
  S ⇒ R: implication, S is a premise or antecedent, R is the conclusion or consequent, also known as a rule or if-then statement.
  S ⇔ R: equivalence or biconditional.
  ¬S : negation.

Constants and symbols are atomic while other sentences are complex. A literal is an atomic sentence or its negation (P, ¬S). The Precedence of operators are ¬, ∧, ∨, ⇒, ⇔.

Propositional Logic Semantics

In simple terms, semantics can be understood as the study of meaning. It focuses on the relationship between the signifiers such as phrases, words, signs and symbols and what they stand for and their donation. True and False indicates the truth and falsity in the world. A proposition denoted that whatever fixed statement about the world we want to know could be true or false. The semantics of complex sentences are derived from the semantics of their parts according to the following truth table.

Or is inclusive. The alternative is exclusive Or: P⊕ Q. The implication is the material implication.

Tautology:

Tautology can be understood as a formula that is true in every possible interpretation. In addition, the definition of tautology can be extended to the sentences in predicate logic which may consist of quantifiers unlike sentences of propositional logic. In propositional logic, there is no distinction between a tautology and a logically valid formula.

A formula of propositional logic is said to be a tautology if the formula itself is always true regardless of which valuation is used for the propositional variables.

Verifying tautologies:

The problem of determining whether a formula is a tautology is fundamental in the propositional logic. If there are n variables occurring in a formula then there are 2ⁿ distinct valuations for the formula. Therefore the task of determining whether the formula is a tautology or not is a finite, mechanical one where one need to only evaluate the truth value of the formula under each of its possible valuations. One algorithmic method for verifying that every valuation causes this sentence to be true is to make a truth table that includes every possible valuation.

For example, consider the formula:

(( A Λ B)→ C) ⇒ (A→ (B→ C)).

There are eight possible valuations for the propositional variables A, B, C, represented by the first three columns of the following table. The remaining columns show the truth of sub-formulas of the formula above, culminating in a column showing the truth value of the original formula under each evaluation.

Validity:

An interpretation is an assignment of True or False to each atomic proposition. A sentence that is true under any interpretation is valid which is also called as the tautology. Validity can be checked by exhaustively exploring each possible interpretation in a truth table.

References:

1. Elaine Rich, Kevin Knight 1991, "Artificial Intelligence".
2. Nilsson, Nils J. Principles of Artificial Intelligence, Narosa Publishing House New Delhi, 1998.
3. Norvig, Peter & Russel, Stuart Artificial Intelligence: A modern Approach, Prentice Hall, NJ, 1995
4. Patterson, Dan W. Introduction to Artificial Intelligence and Expert Systems, Prentice Hall of India Private Limited New Delhi, 1998.