Logic

This text was written in 07/2011 for Semantic Modelling, a course of International media informatics (M) at htw Berlin. It’s an elaboration about Logic.

Introduction

Logic is one of the most important fundamentals of informatics. The branches of informatics needs logic for software-programming, for hardware, for modelling and so on. Certainly logic is required for semantic modelling and semantic web too. Just think about calculability without logic – what would be left?

This elaboration is based on some simple knowledge about logic: You have to know about conjunctions (AND), disjunctions (OR), negation (NOT) and you should have seen some truth-tables. After that there comes some chapters about transformations, proofs, predicate calculus and quantifiers and then we are ready for the cool stuff needed in sophisticated logic calculations and engineering.

If you need more practise please take a look into the first link in sources – there you could find dozens of very good examples with solution process. From there the golden thread is taken and some of the simple examples are so perfect that they taken in fact 1:1 from there. It’s a really good English resource to get into logic. But be aware that some things in logic are in English somewhat different defined as for instance in German. If you take a look in different sources you will find not only differences in description of facts, there are various notations (see below), different symbols for logic gates and the in chapter Minimisation described Karnough map is often defined in other ways, not uncommonly there exists nasty mistakes in how-tos and even in resources published on science-websites and by universities. Without assuming a lack of knowledge it should be clear that mistakes happens quite often in extensive formulas. So for beginners it’s sometimes not so easy to get into this thematic.

To read and comprehend the text we have to define some things first. Here comes the hints about used rules and notations:
From mathematics you know point-calculus before line-calculus. In logic it’s often assumed that the operations are of equal status. In this text we use small variances which are necessary to write complex logic terms a bit shorter. So we define:

  • ¬ is highest-ranking and is ever used for the next character (if there is a bracket after ¬ then the nexus is negated, otherwise the following atomic value)
  • All other nexus (OR, AND, imply, …) are as ever equal-ranking and must be separated appropriate with brackets.
  • There exists many different notations especially for negation. It’s common to write the NOT out or to use the abbreviations ¬ and ! (last for instance in C-like programming languages) and at last there is the possibility of an overline above the negated variable. For large logic terms like the normal forms it’s common to use only the overline. In these cases almost always the AND will be omitted (analogue to multiplication sign in mathematics) and the OR will be written as “+”.

Table of contents

Rules of Inference
Arguments and Proofs
  Slippery Argument
Predicate Calculus
  Universal Quantifier
  Existential Quantifier
Normal Forms (CNF, DNF)
Minimisation
Many-valued logic
Sources

Suggestions, feedback and comments about this logic-elaboration you could write in the German Logik-post.

^ Up to ^ Next >
en-Sites Rules of Inference