Question

In: Computer Science

Discussion - Relationship of digital and mathematical logic In discrete math, you studied a form of...

Discussion - Relationship of digital and mathematical logic

In discrete math, you studied a form of mathematical logic called propositional logic. In this discussion, your task is to research the relationships between propositional logic, Boolean Algebra, and digital logic. Cite your sources and summarize your findings to demonstrate what you learned from the research.

Solutions

Expert Solution

There is a lot of similarity between Propositional logic and Boolean algebraic expressions.

Similar aspects:

1) Both has variables of two states.

2) Operations of Boolean algebra and propositional logic are similar.

3) Simplification of formula expressed in logic can be minimized using Boolean algebra and vice versa.

So let's step back, define them separately, and then look at some interesting examples.

Propositional logic is a branch of mathematics that studies propositions, their truth or falsity, and how they combine.

What you probably think of as "propositional logic" is actually just one kind of propositional logic, namely, classical logic. However, this is not the only kind of classical logic, and not the only one that is interesting in computer science.

Some theories are built on top of classical logic. Presburger arithmetic, for example, is the theory of natural numbers with addition. Tarski arithmetic is the theory of real closed fields. First-order logic is the theory of quantified variables over non-logical objects.

You can think of these logic systems as types of propositional logic, with more axioms to deal with the extra stuff. Many constraint-type problems are expressible in this framework; you can look up satisfiability modulo theories for more information on how this is used.

But there are also propositional logics which are not "classical". One example of a non-classical logic is intuitionistic logic. This is a logic which models constructive proofs, which is interesting, because constructive proofs are the same thing as well-behaved computer programs. ("Well-behaved" in this sense means there is no unbounded recursion.) They are also the basis for modern type systems, such as that of Haskell.

Constructive proofs (e.g. pick any proof from Euclid's Elements) are implementable as computer programs. Given some geometric objects as input, you could implement the proof (at least in principle) as a computer program which performs the construction.

You can't do that with non-constructive proofs. Let's look as an example to see what I mean. I'll prove that there are two irrational numbers, aa and bb, such that abab is rational.

Consider z=2–√2√z=22. This number is either rational or irrational.

Case 1: If zz is rational, then set a=b=2–√a=b=2, and the theorem is proven.

Case 2: If zz is irrational, set a=za=z and b=2–√b=2. Then ab=2ab=2 and the theorem is proven.

QED

The reason why this proof isn't constructive is that it relies on the law of the excluded middle; zz must be either rational or irrational, but we don't (and, in a sense, can't) actually test which of them is true.

Intuitionistic logic systems tend to give you proof systems which are decidable. This is an extremely important practical concern. If you consider, for example, the Java bytecode verifier, or the type system for a programming language (both of which prove that some program is type-correct), they must terminate with an answer, so they must be based on a decidable proof system. By allowing propositions which are neither provable nor refutable, you avoid Gödel-like incompleteness.

That's just one example, of course. Other non-classical propositional logics include modal logics (which can be used to model situations where you have multiple agents who know different things; think about network protocols), and temporal logics (where the truth or falsity of a proposition may change over time).

The thing that connects all of them is the notion of a "proposition". Propositional logic can be thought of as the study of a family of logic systems, all of which deal with the notion of a mathematical statement which has a "truth"-type judgment.

Boolean algebra, on the other hand, is a purely algebraic system, characterised by a set of axioms. Saying "Boolean algebra" is like saying "group" or "field" in abstract algebra. Classical propositional logic satisfies the axioms, but so do other mathematical structures.

The subsets of a set SS, for example, form a Boolean algebra; with the "not" operator corresponding to "set complement", "and" corresponding to "set intersection", and "or" corresponding to "set union". You can think of "true" as being SS and "false" being the empty set, but these are not the only "truth values" which the system models.

Lattices form Boolean algebras, and some lattices are important in computer science (e.g. Scott domains). Moreover, some important non-classical logic-like systems naturally form Boolean algebras, such as fuzzy logic.

So what I hope you can see is that while the two notions are related (some Boolean algebras model some propositional logics), they are not exactly the same thing. How they differ is part of what makes them interesting.

Digital Logic and Boolean algebra

Introduction

We now tackle the lowest of the six levels mentioned in the introduction -- the digital logic level.

Digital:

means that we are dealing with `digits', i.e. discrete quantities as opposed to continuous or analogue quantities;

Logic:

indicates that the electronics is implementing a form of mathematics based on logic - propositional logic.

First we will introduce propositional logic - `Boolean algebra'. Then we will show how simple logic (Boolean) functions are implemented in computer hardware.

Logic

Introduction

Since at least 400 B.C. human beings have been studying what it means to think and to reason. Two closely related aims can be identified:

  • To understand the process of mental reasoning.
  • To develop methods to mechanise thinking and reasoning, e.g. to develop procedural methods for doing mathematical proofs, or simply to give procedures by which a thinker could come up with a rational answer to a difficult question, or, more lately, as in the study of Artificial Intelligence, to develop methods by which computers may be programmed to perform tasks that require intelligence.

Broadly speaking, logic is the study of the principles and patterns of reasoning, argument and proof. Again generalising, we can say that logic uses a language that is a formalisation of certain types of natural language statements.

You should be aware that there are two distinct but related forms of logic:

  • Propositional logic - which is closely related to Boolean algebra. We will have cause to use elements of propositional logic in this course. And, you will come across it frequently in your other courses. Note: in programming, where you will have already come across statements like: if(x == 10 && y == 20) (test the truth of the logic statement x is-equal-to 10 and y is-equal-to 20.
  • Predicate calculus, which is at the basis of the Prolog programming language.

Propositional Logic

Propositional logic deals with statements (propositions) which make claims which can be either true or false. Thus, valid propositions are:

  • Dublin is the capital of Ireland.
  • Belfast has more than 100,000 inhabitants.
  • Manchester United are Premiership Champions.
  • Joe Bloggs is a first year QUB student.

The test for validity is as follows: you must be able to meaningfully append to the statement "is true" (or "is false").

Thus "Dublin is the capital of Ireland is true".

Notice, however, how "Manchester United are Premiership Champions" may need time/date qualification.

The following are invalid propositions.

  • What is the capital of Ireland? (a question)
  • Has Dublin a large population? (a question)
  • Go now to room 1.15! (a command)
  • Will you come to the Botanic Inn with me on Thursday? An invitation - variations on which may be called a "proposition" in everyday language!

Generalisation/Abstraction: Symbolic Logic

Compound Propositions

We can now combine elementary propositions using logic connectives to make compound or complex propositions.

1, Conjunction - and

Dublin is the capital of Ireland and Belfast has more than 100,000 inhabitants is true.

The combined proposition is true if-and-only-if both elements are true.

In this case, let us agree that both are true, so that the statement:

Arsenal are European Champions and Belfast has more than 100,000 inhabitants is false.

The meaning of and can be neatly summarised with a truth-table using abstract symbols:

p

q

F

F

F

F

T

F

T

F

F

T

T

T

2, Disjunction - or

Note that or has two natural language meanings: exclusive-or, only one of the statements can be true at any time; inclusive-or, only either one or the other needs be to be true, or both; without any qualification, or generally means inclusive-or.

The meaning of or is given by the following truth-table:

p

q

F

F

F

F

T

T

T

F

T

T

T

T

3, Negation - not

If a proposition p is true, then not(p) is false.

The meaning of not is given by the truth-table:

p

F

T

T

F

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


Related Solutions

Discrete math problem: Prove that there are infinitely many primes of form 4n+3.
Discrete math problem: Prove that there are infinitely many primes of form 4n+3.
It is a discrete math problem about probability: You flip a nickel (5 cents coin) and...
It is a discrete math problem about probability: You flip a nickel (5 cents coin) and roll a six-sided die. Points are assigned as follows. The nickel showing heads is worth 1 point and the nickel showing tails is worth 5 points. The points for the die correspond simply to the number on its upper surface. Each outcome is equally likely and we define the following events. A: The sum of points is greater than 7. B: The sum of...
It is a discrete math problem about probability: You flip a nickel (5 cents coin) and...
It is a discrete math problem about probability: You flip a nickel (5 cents coin) and roll a six-sided die. Points are assigned as follows. The nickel showing heads is worth 1 point and the nickel showing tails is worth 5 points. The points for the die correspond simply to the number on its upper surface. Each outcome is equally likely and we define the following events. A: The sum of points is greater than 7. B: The sum of...
In this chapter you studied the normal distribution which will form the basis for the remainder...
In this chapter you studied the normal distribution which will form the basis for the remainder of the course. Having a firm understanding of this distribution is very important. In this post you are required to do two things. 1. Write at least one good paragraph that explains (in your own words) what the normal distribution is. Explain it as if your were trying to explain it to someone who did not know anything about the distribution. Include all important...
Discrete Math answer question 2 only 1) You have 10 identical snails you want to feed...
Discrete Math answer question 2 only 1) You have 10 identical snails you want to feed to your 4 starfish (named SFA, SFB, SFC, and SFD). a. One way to distribute the snails is to give 3 snails to SF-A, 2 snails to SF-B, 0 snails to SF-C, and 5 snails to SF-D. How would you represent this outcome as a stars-and-bars diagram? b. How many ways are there to distribute the snails all together? Briefly explain. c. How many...
You have studied a number of mathematical structures. Vector space, metric space, topo- logical space, group,...
You have studied a number of mathematical structures. Vector space, metric space, topo- logical space, group, ring and field are some examples. Give general definitions and specific examples. Comment on some of the details of some of these structures. Explain how various kinds of functions are involved in these structures.
In this discussion question you will discuss the corporate form of business organization: What are the...
In this discussion question you will discuss the corporate form of business organization: What are the advantages and disadvantages of the corporate form of business organization? How does the corporate form of organization compare to sole proprietorships and partnerships? What are the advantages and disadvantages of each? If you were to start a business today, which of these forms of business organization would you chose? What would be the single deciding factor that would help you in your decision? Why?
You are surrounded by some form of digital art most of your day. Discuss your definition...
You are surrounded by some form of digital art most of your day. Discuss your definition of digital art. What forms of digital art do you encounter on a regular basis? which do you like, which do you dislike, and why with pictures?
In this discussion talk about digital forensics examining cases. What tools and software can you use?...
In this discussion talk about digital forensics examining cases. What tools and software can you use? What evidence might you find in computers or other crime scenes? Add any useful insight that you might have.
Go to the discussion room and tell me what form of business ownership you have chosen...
Go to the discussion room and tell me what form of business ownership you have chosen for your imaginary business. You must tell me why you chose that form of ownership, listing two or three of the advantages of that form of ownership, and also listing two or three of the disadvantages of that form of ownership. You must then describe one of the forms of business ownership that you did NOT choose for your business, and tell me why...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT