Understanding the concepts of basic logic while you pursuing in the field of computer science is more like you are strengthening your roots to the ground. Logic studies how information is captured in sentences and how it is possible for one statement to be the outcome of the other. For instance, logics are used to design the digital circuits, knowledge representation is based on logical formalisms.
What Is Propositional Logic
Propositional logic is a simple form of logic which is also known as Boolean logic. A proposition has TRUTH values (0 and 1) which means it can have one of the two values i.e. True or False. It is the most basic and widely used logic. This logic is used for the development of powerful search algorithms including implementation methods. Mathematically, logical operators combine propositions to make other propositions by following some specific rules.
Propositional logic is used in artificial intelligence for planning, problem-solving, intelligent control and most importantly for decision-making. It is all about Boolean functions and the statements where there are more than just true and false values, includes the certainty as well as uncertainty, it led to the foundation for machine learning models. It is a useful tool for reasoning, but it has limitation because it cannot see inside prepositions and take advantage of relationships among them.
Properties
- Satisfiable: A atomic propositional formula is satisfiable if there is an interpretation for which it is true.
- Tautology: A propositional formula is valid or a tautology it is true for all possible interpretations.
- Contradiction: A propositional formula is contradictory (unsatisfiable) if there is no interpretation for which it is true.
- Contingent: A propositional logic can be contingent which means it can be neither a tautology nor a contradiction.
Standard Theorems Of Propositional Logic
Assuming p, q, and r represent the propositions which can be true or false and they are chosen arbitrarily. The list of standard theorems in propositional logic are as follows
1| p, q => p ∧ q
2| p, p → q => q (Modus Ponens)
3| ¬p, p ∨ q => q (law of disjunctive inference)
4| ¬q, p → q => ¬p (Modus Tollens)
5| p ∨ q, p → r, q → r => r
6| p → q, q → r => p → r (Chaining)
7| p, p → q, q → r => r (Modus Ponens & Chaining)
8| p ∨ ( q ∧ ¬q ) ⇔ p
9| p ∧ ( q ∨ ¬q ) ⇔ p
10| p → q ⇔ ¬p ∨ q
11| ¬( p → q ) ⇔ p ∧ ¬q
12| p ↔ q ⇔ ( p → q ) ∧ ( q → p ) (Bidirectional elimination)
13| p ↔ q ⇔ ( p ∧ q ) ∨ ( ¬p → ¬q )
14| p → ( q → r ) ⇔ ( p ∧ q ) →r
15| p → q ⇔ ¬q → ¬p (Contraposition theorem)
What is Predicate Logic Or First-Order Logic
Predicate logic is a collection of formal systems which uses quantified variables over non-logical objects and allows the use of sentences which contain variables.
Difference Between Them
Besides the propositional logic, there are other logics as well such as predicate logic and other modal logics. Propositional logic provides more efficient and scalable algorithms than the other logics. There are few differences between the propositional logic and first-order logic, some of them are mentioned below.
- Propositional logic deals with simple declarative propositions, while first-order logic additionally covers predicates and quantification.
- A proposition is a collection of declarative statements that has either a truth value “true” or a truth value “false”. While a predicate logic is an expression of one or more variables defined on some specific domain.
References:
