Logical Representation

Image via Wikipedia

• Propositional logic

Propositional logic, also known as sentential logic and statement logic, is the branch of logic that studies ways of joining and/or modifying entire propositions, statements or sentences to form more complicated propositions, statements or sentences, as well as the logical relationships and properties that are derived from these methods of combining or altering statements. In propositional logic, the simplest statements are considered as indivisible units, and hence, propositional logic does not study those logical properties and relations that depend upon parts of statements that are not they statements on their own, such as the subject and predicate of a statement. The most thoroughly researched branch of propositional logic is classical truth-functional propositional logic, which studies logical operators and connectives that are used to produce complex statements whose truth-value depends entirely on the truth-values of the simpler statements making them up, and in which it is assumed that every statement is either true or false and not both. However, there are other forms of propositional logic in which other truth-values are considered, or in which there is consideration of connectives that are used to produce statements whose truth-values depend not simply on the truth-values of the parts, but additional things such as their necessity, possibility or relatedness to one another.

• Predicate logic

The propositional logic is not powerful enough to represent all types of assertions that are used in computer science and mathematics, or to express certain types of relationship between propositions such as equivalence.

For example, the assertion “x is greater than 1”, where x is a variable, is not a proposition because you cannot tell whether it is true or false unless you know the value of x. Thus, the propositional logic cannot deal with such sentences. However, such assertions appear quite often in mathematics and we want to do inferencing on those assertions.

In addition, the pattern involved in the following logical equivalences cannot be captured by the propositional logic:

• “Not all birds fly” is equivalent to “Some birds don’t fly”.
• “Not all integers are even” is equivalent to “Some integers are not even”.
• “Not all cars are expensive” is equivalent to “Some cars are not expensive”

Each of those propositions is treated independently of the others in propositional logic. For example, if P represents “Not all birds fly” and Q represents “Some integers are not even”, then there is no mechanism in propositional logic to find out the P is equivalent to Q. Hence, to be used in inferencing, each of these equivalences must be listed individually rather than dealing with a general formula that covers all these equivalences collectively and instantiating it as they become necessary, if only propositional logic is used.

Thus we need more powerful logic to deal with these and other problems. The predicate logic is one of such logic and it addresses these issues among others.

• First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names; including first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic. First-order logic is distinguished from propositional logic by its use of quantifiers; each interpretation of first-order logic includes a domain of discourse over which the quantifiers range.

There are many deductive systems for first-order logic that are sound (only deriving correct results) and complete (able to derive any logically valid implication). Although the logical consequence relation is only semi decidable, much progress has been made in automated theorem proving in first-order logic. First-order logic also satisfies several meta-logical theorems that make it amenable to analysis in proof theory, such as the Löwenheim Skolem theorem and the compactness theorem.

First-order logic is of great importance to the foundations of mathematics, where it has become the standard formal logic for axiomatic systems. It has sufficient expressive power to formalize two important mathematical theories: Zermelo Fraenkel set theory (ZF) and first-order Peano arithmetic. However, no axiom system in first order logic is strong enough to fully (categorically) describe infinite structures such as the natural numbers or the real line. Categorical axiom systems for these structures can be obtained in stronger logics such assecond-order logic.