Logic vs Computer science- a perspective

HSS F236 – Symbolic Logic

Logic and Computer Science

Submitted as a partial fulfilment of the course HSS F236 Symbolic Logic By V Chandrakanth 2012C6PS638P Sai Krishna 2012C6PS689P

Logiter (Logic + Computer)* Science *it is not a typo- this indicates that Logic and Computer Science can never be seperable.

Introduction: From the starting phrase “According to the given problem” to the ending phrase “Hence Proved”, Logic is everywhere in Computer Science. Computer science is just the technical implementation of Logic, thus justifying the phrase “Logic is the Science of Engineering”.

Applications of Logic in Computers: Computer Science has its foundations built on logic and set theory. Ranging from Programming Languages, Mathematical induction , designing Compilers, state diagrams , trees structures of data, logic has a vast range of applications in Computer science.

Prolog: Have you ever imagined that an application you use daily, or our own ERP Portal is completely built with two simple logical derivatives. Yes, Logic has made it possible in Computer Science to define a new programming language paradigm with the name PROLOG(PROgraming LOGic). This language was built by the desire to reconcile the use of logic as a declarative knowledge representation language with the procedural representation of knowledge This simple language is built on two simple logical derivatives. A Premise (called Fact here )and a Conditional Statement(called Rules here). Using the recursion principle, the conditional statement is recursively associated with another such statement making it a cycle and here is where we use logical techniques like Deductive Top to Bottom or Inductive Bottom to Top approaches to deduce the logic of the language. e.g.,

Fact in plain english: Tom is a cat. In Prolog: cat(tom). Rule in plain english: Cat is an animal

In Prolog: animal(X) :- cat(X)

And, similar to check whether a statement is a tautology or not? In prolog, we have, ?- cat(tom). Ans: Yes

2012C6PS638P – 2012C6PS689P

HSS F236 – Symbolic Logic

Logic and Computer Science

Theory of Computation: A Programming Language being the building block of Computer Science, follows a logical strucutre, where every such programming language is expressed in terms of Finite Automated Structures, in which every single term in the language is assumed to be a state and a state transfer is associated with a logic.

The above Finite Automata indicates that A term is considered as a variable if and only if it starts with a letter from the range [a-z] or [A-Z].

Computational Tree Logic: In most of the computer programming applications, computational tree logic is used where in the state of the computer(values of all the attributes assumed a system contains at a given point of time) changes over time and is represented in terms of trees. Computation trees are derived from state transition graphs. The graph structure is unwound to n infinite tree rooted at the initial stage which follows a deductive top to bottom logic. The below diagram shows an illustration of unwinding a graph into a tree based on a simple fact or premise (called thumb rule), that every state can be unwinded infinite no. of times and at some or other place the tree has to end. So, every aspect in the computational trees is tightly bonded with logic.

Paths in the above tree represent all possible computations of the system being modelled.

2012C6PS638P – 2012C6PS689P

HSS F236 – Symbolic Logic

Logic and Computer Science

Non-Monotonic Logic: A non-monotonic logic is a logic whose consequence relation is not monotonic. Having a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. Intuitively, monotonicity indicates that learning a new piece of knowledge cannot reduce the set of what is known. A monotonic logic cannot handle various reasoning tasks such as reasoning by default (consequences may be derived only because of lack of evidence of the contrary), abductive reasoning (consequences are only deduced as most likely explanations), some important approaches to reasoning about knowledge (the ignorance of a consequence must be retracted when the consequence becomes known), and similarly, belief revision (new knowledge may contradict old beliefs). The Nixon Diamond Example: A famous example from the literature, the so-called "Nixon diamond," will help make the distinction clear. Suppose our knowledge base contains (defeasible) information to the effect that a given individual, Nixon, is both a Quaker and a Republican. Quakers, by and large, are pacifists, whereas Republicans, by and large are not. The question is what defeasible conclusions are warranted on the basis of this body of knowledge, and in particular whether we should infer that Nixon is a pacifist or that he is not pacifist. The following figure provides a schematic representation of this state of affairs in the form a (defeasible) network:

The reasoner has no reason to prefer either conclusion ("Nixon is a pacifist;" "Nixon is not a pacifist") to the other one, but will definitely commit to one or the other. The reasoner recognizes that this is a conflict not between hard facts and defeasible inferences, but between two different defeasible inferences. Since the two possible inferences in some sense "cancel out," the sceptical reasoner will refrain from drawing either one.

2012C6PS638P – 2012C6PS689P

HSS F236 – Symbolic Logic

Logic and Computer Science

All Horses are of the Same colour: Before going to the this paradox, a brief introduction to mathematical induction a basement of Computer Science is needed. Mathematical Induction is one of those proving methods which is used to prove major formulas or major hypothesis to be true, by considering simple cases starting from n = 1 to n = some k. Below is a paradox which claims that all the horses on earth are of the same colour, which clearly indicates the MAGIC OF LOGIC. The horse paradox is a falsidical paradox that arises from flawed demonstrations, which purport to use mathematical induction, of the statement “All horses are the same colour”. One major application of logic to be observed here is the premise assumed to be taken and the conclusion we are arriving on. Base case: One horse The case with just one horse is trivial. If there is only one horse in the "group", then clearly all horses in that group have the same colour. Inductive step Assume that n horses always are the same colour. Let us consider a group consisting of n+ 1 horse. First, exclude the last horse and look only at the first n horses; all these are the same colour since n horses always are the same colour. Likewise, exclude the first horse and look only at the last n horses. These too, must also be of the same colour. Therefore, the first horse in the group is of the same colour as the horses in the middle, which in turn are of the same colour as the last horse. Hence the first horse, middle horses, and last horse are the entire same colour, and we have proven that: “If n horses have the same colour, then n+ 1 horse will also have the same colour.” We already saw in the base case that the rule ("all horses have the same colour") was valid for n=1. The inductive step showed that since the rule is valid for n=1, it must also be valid for n=2, which in turn implies that the rule is valid for n=3 and so on.

Actual Situation

The Magic of Logic- All horses brought to be of the same colour

2012C6PS638P – 2012C6PS689P

HSS F236 – Symbolic Logic

Logic and Computer Science

Logic of Infons: The Logic of Infons is a recent development in the channel of logic and computer science. Infons are statements viewed as containers of information (rather than representations of truth values). The logic of infons turns out to be a conservative extension of logic known as constructive or intuitionistic. Distributed Knowledge Authorization Language uses additional unary connectives “p said” and “p implied” where p ranges over principals. Infons are statements, that is declarative statements, viewed as containers of information, for example, John has the right to read File 13 of the given computer system. We don’t ask whether an infon is true or false. Instead we ask whether it is known to relevant principals. For example, “does the owner of File 13 know that John has the right to read the file?” “Does the administrator of the system know?” “Does John know?” Besides, the notion of infon is purely semantic. The term Infons was already used in situation theory (nothing to do with the progress of this assignment) in the past. But infons are assigned truth values in situation theory, so our usage of the term is quite different.

Conclusion: The Logic is so much into computer science that no connecting channel exists but logic and computer science can never be treated as two separate entities. Logic gave computer science it’s beauty, beauty is never meant to be exterior characteristics but the inner beauty of computer science is laid on logic. As we have fallacies in normal logic , we also have paradoxes in computer science but proper structuring gave it the form that it contains today.

2012C6PS638P – 2012C6PS689P

HSS F236 – Symbolic Logic

Logic and Computer Science

References 1. Yuri Gurivech - Logic of Infons : the Propositional Case 2. Stanford Encyclopedia of Philosophy- An article on Non-Monotonic Logic 3. Enumerative Combinatorics by George - Mathematical Induction Paradoxes. 4. L Amaru, A Chattopadhay – A Sound and Complete Axiomization of Majority – nLogic. 5. Michael Huth and ryan Logic in Computer Science 6. Alfred V.Aho,Ravi Sethi - Compiler Principles ,Techniques and Techniques 7. Wikipedia – Non-monotonic Logic

2012C6PS638P – 2012C6PS689P