Evolution of Logic in Informatics and Computer Science
Explore the journey of logic from philosophical debates in ancient times to its crucial role in computer science today. From symbolic logic to mathematical foundations, discover how logic has shaped the development of formal systems and applications in various fields within the realm of informatics and computer science.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Logic of Informatics Introduction
Historical view Philosophical Logic 500 BC to 19th Century Symbolic Logic Mid to late 19th Century Mathematical Logic Late 19thto mid 20thCentury Logic in Computer Science
Logic is called the CALCULUS of Computer Science! LOGIC is a term for CS CALCULUS is a term for Physical sciences & Engineering Disciplines Many CS areas use LOGIC, such as: Architecture (logic gates) Programming Languages ( Semantics & Logic Programming) AI Databases (SQL)
Philosophical Logic 500 B.C 19th Century Logic dealt with arguments in the natural language used by humans. Example All men are mortal. Socrates is a man Therefore, Socrates is mortal.
Philosophical Logic [2] Natural languages are very ambiguous. Eric does not believe that Mary can pass any test. ...does not believe that she can pass some test, or ...does not believe that she can pass all tests I only borrowed your car. And not borrowed and used , or And not car and coat Tom hates Jim and he likes Mary. Tom likes Mary, or Jim likes Mary
Symbolic Logic Mid to late 19th Century. The modern development of symbolic logic begin with George Boole in the 19th century. Attempted to formulate logic in terms of a mathematical language Rules of inference were modeled after various laws for manipulating algebraic expressions.
Mathematical Logic Late 19thto mid 20thCentury Frege proposed logic as a language for mathematics in 1879. With the rigor of this new foundation, Cantor was able to analyze the notion of infinity in ways that were previously impossible. (2Nis strictly larger than N) Russell s Paradox T = { S | S S}
Logic in Computer Science In computer science, we design and study systems through the use of formal languages that can themselves be interpreted by a formal system. Boolean circuits Programming languages Design Validation and verification AI, Security. Etc.
Logic in Computer Science Propositional Logic First Order Logic Higher Order Logic Theory of Construction Real-time Logic, Temporal Logic Process Algebras Linear Logic
Propositions Logic A proposition is a statement that is either true or false 2+2=4 (true) New York City is in Oregon (false) Today is Friday (its either true or false) Do your homework! (not a proposition)
Compound and Primitive Propositions Compound Propositions are propositions that are composed of sub-propositions connected together in various ways roses are red and violets are blue Mark is smart or he studies a lot A (atomic, elementary) proposition is the underlying meaning of a simple declarative sentence, which is either true or false
Predicate logic Extension of propositional logic A predicate is just a property Predicates define relationships between any number of entities using qualifiers: for all , for every there exists
Example Let P(x) be the property if x is a triangle then the sum of its internal angles is 180o In predicate logic: x P(x) For every x such that x is a triangle, the sum of the internal angles of x is 180o
Another example Let P(x) be the property x is an integer and x2= 4 Then x P(x) There exists x such that x is an integer and x2 = 4
Newtons second law of motion of type called object for every x or x: Object stationary(x) in-uniform-motion (x) f : Force x is-acted-upon-by f there exists an f In English: for every x of a certain type referred to as an Object, x is stationary, x is in uniform motion, or there is an f of type Force such that x is acted upon by f
and Remember: x for every x , or for All x x there is an x or there Exists an x Tip: Think of as an upside down A ( for All ) Think of as a backwards E ( there Exists )
Propositional connectives These are the words that we use to join atomic propositions together to form compound propositions. E.G: In 1938 Hitler seized Austria, (and) in 1939 he seized former Czechoslovakia and in 1941 he attacked the former USSR while still having a non-aggression pact with it
Propositional connectives Propositional logic has four connectives Name Read as Symbol negation not conjunction and disjunction or implication if then
Interpretation of connectives Connective Interpretation negation pis true if and only if p is false A conjunction p q is true if and only if both p and q are true A disjunction p q is true if and only if p is true or q is true. An implication p q is false if and only if p is true and q is false The biconditional p if and only if q is written p q
Some more terminology Expressions either side of a conjunction are called conjuncts (p q) Expressions either side of a disjunction are called disjuncts (p q) In the implication p q, p is called the antecedent and q is the consequence
Precedence of connectives In complex propositions, brackets may be used to remove ambiguity. (p q) r versus p (q r) By convention, the order of precedence Brackets, Negation, Conjunction, Disjunction, Implication
Mathematical Logic Statement Formulas Definitions Symbols p ,q ,r ,...,called statement variables Symbols ~, , , ,and connectives 1) A statement variable is a statement formula 2) If A and B are statement formulas, then the expressions (~A ), (A B) , (A B ), (A B ) and (A B ) are statement formulas Expressions are statement formulas that are constructed only by using 1) and 2) above are called logical Discrete Mathematical Structures: Theory and Applications 22
Formalisation Although both Stanley and Gordon are not young, Stanley has a better chance of winning the next bowling tournament, despite Gordon s considerable experience
Formalisation (continued) Atomic propositions: p Stanley is young q Gordon is young r Stanley has a better chance of winning the next bowling tournament s Gordon has considerable experience in bowling Formalisation in Propositional Logic: ( p) ( q) r s
Truth Table A truth table for a compound statement is a list of the truth or falsity of the statement for every possible combination of truth and falsity of its components. In other words, a truth table helps to show whether a statement is true or false.
Rows To find the number of rows used in a truth table, take the number 2 raised to the power of the number of variables. For example, if there was a p statement and a q statement, there would be 2 variables, 2^2 is 4. If there were three statements, it would be 2^3, or 8 rows.
Columns The columns under the connectives /\, and \/, stand for the conjunction, and disjunction of the expression on the two sides of that connective.
Negation Truth Table p ~ p The opposite of p is ~p T F Not true is false F T Not false is true
Conjunction Truth Table p q p /\ q p and q True only if both are true. T T T T F F F T F F F F
Disjunction Truth Table p q p \/ q p or q True if either on is true T T T T F T F T T False only if both are false F F F
Logical implication: IMPLIES Is a proposition if p, then q . Produces all true values except when p is true and q is false. Keywords: if-then, if, then, whenever, only if, etc. We often use p q The Truth table of p q All true except when p is true and q is false. 9/28/2024 31
Biimplication Let p and q be statements. The statement p if and only if q is called the biimplication or biconditional of p and q The biconditional p if and only if q is written p q p q is read: p if and only if q p is necessary and sufficient for q q if and only if p q when and only when p Discrete Mathematical Structures: Theory and Applications 32
Biconditional [2] Truth Table for the Biconditional: Discrete Mathematical Structures: Theory and Applications 33
Construct truth-tables for each of the following formulae: 1. P & (Q v P) 2. P Q 3. Q v (P & Q) 4. P (P & Q) 5. P (P v Q) 6. Q (P Q) 7. P & P 8. (Q v P) & P
