UNIT 2

Natural Deduction

Natural Deduction is a logical reasoning system used to derive conclusions from premises using a set of inference rules. It helps in proving mathematical theorems and validating arguments in propositional and predicate logic. The goal is to derive a conclusion step-by-step, following logical principles.

Key Features of Natural Deduction

1. Rule-Based System – Uses logical inference rules such as modus ponens, modus tollens, conjunction, disjunction, etc.
   
   

2. Step-by-Step Proofs – Proves theorems by breaking them into smaller, valid steps.
   
   

3. Used in Logic and Mathematics – Applied in formal proofs, AI reasoning, and automated theorem proving.
   
   

4. Two Main Types of Rules:
   
   

   • Introduction Rules – Introduce new logical operators (e.g., AND, OR, NOT).
     
     

   • Elimination Rules – Remove logical operators to simplify expressions.

Example of Natural Deduction

Given Premises:

1. If it rains, the ground is wet. (R → W)

2. It is raining. (R)

Step-by-Step Deduction:

• Step 1: R (Premise)

• Step 2: R → W (Premise)

• Step 3: W (Conclusion, using Modus Ponens)

Thus, we deduce that the ground is wet.

Conclusion

Natural Deduction provides a systematic way to derive conclusions using logical rules. It is widely used in mathematics, computer science, and philosophy to validate arguments and construct proofs logically.

Computable Functions and Predicates in AI

In Artificial Intelligence (AI) and computability theory, computable functions and predicates play a crucial role in defining what problems can be solved using algorithms.

Computable Functions

A computable function is a function that can be evaluated using a step-by-step algorithm in a finite amount of time. It takes an input, processes it, and produces an output following a well-defined procedure.

Key Features:

1. Definable by Algorithms – Can be implemented in a programming language.

2. Finite Steps – Must complete execution in a limited number of steps.

3. Examples in AI – Used in search algorithms, decision-making, and machine learning.
   
   

Example:

A function that calculates the square of a number:

f(x) = x²

If x = 3, then f(3) = 3² = 9 (computed in finite steps). 

Computable Predicates

A computable predicate is a logical function that returns true or false based on an input. It is used in AI for decision-making, classification, and rule-based systems.

Key Features:

1. Binary Output – Returns True (1) or False (0).

2. Used in Logical Reasoning – Helps AI make decisions.

3. Examples in AI – Used in expert systems, constraint satisfaction problems, and machine learning models.

Example:

A predicate to check if a number is even:

P(x) = (x mod 2 == 0)

• P(4) = True (4 is even)

• P(5) = False (5 is odd)

Conclusion

Computable functions and predicates are essential in AI for defining rules, making decisions, and solving problems efficiently through algorithms.