Share
VIDEOS 1 TO 50
Boolean Logic & Logic Gates: Crash Course Computer Science #3
Boolean Logic & Logic Gates: Crash Course Computer Science #3
Published: 2017/03/08
Channel: CrashCourse
From logic to computer science: a linguistic journey
From logic to computer science: a linguistic journey
Published: 2013/12/10
Channel: The Royal Society
Lec 1 | MIT 6.042J Mathematics for Computer Science, Fall 2010
Lec 1 | MIT 6.042J Mathematics for Computer Science, Fall 2010
Published: 2012/12/31
Channel: MIT OpenCourseWare
And Logic Begat Computer Science: When Giants Roamed the Earth
And Logic Begat Computer Science: When Giants Roamed the Earth
Published: 2014/04/24
Channel: Eric Smalls
AND OR NOT - Logic Gates Explained - Computerphile
AND OR NOT - Logic Gates Explained - Computerphile
Published: 2015/03/06
Channel: Computerphile
How To Get Better At Programming Logic?
How To Get Better At Programming Logic?
Published: 2017/02/17
Channel: Simple Programmer
IGCSE Computer Science Tutorial: 1.3.1 (a) – Logic Gates
IGCSE Computer Science Tutorial: 1.3.1 (a) – Logic Gates
Published: 2016/01/28
Channel: Liam McQuay
Logic 101 (#1): Introduction
Logic 101 (#1): Introduction
Published: 2013/10/31
Channel: William Spaniel
Logic in Computer Science, Engineering and Industry
Logic in Computer Science, Engineering and Industry
Published: 2016/11/10
Channel: Simons Institute
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 2
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 2
Published: 2016/08/24
Channel: Joohyung Lee
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 3
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 3
Published: 2016/08/26
Channel: Joohyung Lee
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 15
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 15
Published: 2016/10/14
Channel: Joohyung Lee
How Computers Calculate - the ALU: Crash Course Computer Science #5
How Computers Calculate - the ALU: Crash Course Computer Science #5
Published: 2017/03/22
Channel: CrashCourse
Mathematical Logic for Computer Science
Mathematical Logic for Computer Science
Published: 2016/06/12
Channel: charlene
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 4
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 4
Published: 2016/08/31
Channel: Joohyung Lee
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 1
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 1
Published: 2016/08/19
Channel: Joohyung Lee
Lecture 1 - Propositional Logic
Lecture 1 - Propositional Logic
Published: 2007/12/04
Channel: nptelhrd
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 12
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 12
Published: 2016/09/28
Channel: Joohyung Lee
IGCSE Computer Science Tutorial: 1.3.1 (d) – Solving Problems with Logic Gates
IGCSE Computer Science Tutorial: 1.3.1 (d) – Solving Problems with Logic Gates
Published: 2016/01/30
Channel: Liam McQuay
Registers and RAM: Crash Course Computer Science #6
Registers and RAM: Crash Course Computer Science #6
Published: 2017/03/29
Channel: CrashCourse
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 16
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 16
Published: 2016/10/19
Channel: Joohyung Lee
1.5.1 Predicate Logic 1: Video
1.5.1 Predicate Logic 1: Video
Published: 2016/09/12
Channel: MIT OpenCourseWare
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 23
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 23
Published: 2016/11/16
Channel: Joohyung Lee
Computer Science Ep.14 - Intro To Logic Gates
Computer Science Ep.14 - Intro To Logic Gates
Published: 2013/12/26
Channel: CodingForCats
Logic in Computer Science Modelling and Reasoning about Systems
Logic in Computer Science Modelling and Reasoning about Systems
Published: 2016/04/02
Channel: zubian
Propositional Logic: Introduction
Propositional Logic: Introduction
Published: 2009/12/01
Channel: Kevin deLaplante
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 19
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 19
Published: 2016/10/28
Channel: Joohyung Lee
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 14
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 14
Published: 2016/10/05
Channel: Joohyung Lee
Edexcel GCSE Computer Science: Logic - Topic 17
Edexcel GCSE Computer Science: Logic - Topic 17
Published: 2016/03/19
Channel: Computer Science Tutor
01 Introduction to Digital Logic
01 Introduction to Digital Logic
Published: 2016/08/15
Channel: UGC NET Computer Science CSE
Computer Science Ep. 15 - Boolean Expressions(Logic Gates)
Computer Science Ep. 15 - Boolean Expressions(Logic Gates)
Published: 2013/12/26
Channel: CodingForCats
OCR GCSE Computing: Binary Logic Circuits - Topic 3
OCR GCSE Computing: Binary Logic Circuits - Topic 3
Published: 2014/10/27
Channel: Computer Science Tutor
Mathematical Logic for Computer Science
Mathematical Logic for Computer Science
Published: 2016/04/02
Channel: loretta
Logic in Computer Science Modelling and Reasoning about Systems
Logic in Computer Science Modelling and Reasoning about Systems
Published: 2017/03/24
Channel: Kyle Hudson
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 20
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 20
Published: 2016/11/02
Channel: Joohyung Lee
Logic in Computer Science Modelling and Reasoning about Systems
Logic in Computer Science Modelling and Reasoning about Systems
Published: 2016/02/26
Channel: flanagan
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 17
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 17
Published: 2016/10/21
Channel: Joohyung Lee
Fuzzy Logic - Computerphile
Fuzzy Logic - Computerphile
Published: 2014/06/11
Channel: Computerphile
IGCSE Computer Science Tutorial: 1.3.1 (b) – Creating Logic Circuits
IGCSE Computer Science Tutorial: 1.3.1 (b) – Creating Logic Circuits
Published: 2016/01/29
Channel: Liam McQuay
AP Computer Science Video Lecture: Boolean Logic
AP Computer Science Video Lecture: Boolean Logic
Published: 2013/10/12
Channel: Won Oh
Logic in Computer Science Modelling and Reasoning about Systems
Logic in Computer Science Modelling and Reasoning about Systems
Published: 2016/03/01
Channel: wrighty
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 5
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 5
Published: 2016/09/02
Channel: Joohyung Lee
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 10
ASU CSE 294 Logic in Computer Science (Fall 2016) Lecture 10
Published: 2016/09/21
Channel: Joohyung Lee
Logic in Computer Science Modelling and Reasoning about Systems
Logic in Computer Science Modelling and Reasoning about Systems
Published: 2017/03/07
Channel: Arleta R.
Truth Table Tutorial - Discrete Mathematics Logic
Truth Table Tutorial - Discrete Mathematics Logic
Published: 2014/03/26
Channel: Emily Jane
Free Download Logic in Computer Science Modelling and Reasoning about Systems
Free Download Logic in Computer Science Modelling and Reasoning about Systems
Published: 2017/03/04
Channel: E. Sanzyo
Free Download Logic for Computer Science and Artificial Intelligence
Free Download Logic for Computer Science and Artificial Intelligence
Published: 2017/03/04
Channel: E. Sanzyo
Jean Yang on An Axiomatic Basis for Computer Programming
Jean Yang on An Axiomatic Basis for Computer Programming
Published: 2014/12/26
Channel: PapersWeLove
Ian Barland: Logic: The Foundation of Computer Science
Ian Barland: Logic: The Foundation of Computer Science
Published: 2014/06/13
Channel: Logic and Reasoning Institute at James Madison University
OCR GCSE Computing: Binary Logic - Topic 3
OCR GCSE Computing: Binary Logic - Topic 3
Published: 2014/10/27
Channel: Computer Science Tutor
NEXT
GO TO RESULTS [51 .. 100]

WIKIPEDIA ARTICLE

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Diagrammatic representation of computer logic gates

Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas:

  • Theoretical foundations and analysis
  • Use of computer technology to aid logicians
  • Use of concepts from logic for computer applications

Theoretical foundations and analysis[edit]

Logic plays a fundamental role in computer science. Some of the key areas of logic that are particularly significant are computability theory (formerly called recursion theory), modal logic and category theory. The theory of computation is based on concepts defined by logicians and mathematicians such as Alonzo Church and Alan Turing.[1][2] Church first showed the existence of algorithmically unsolvable problems using his notion of lambda-definability. Turing gave the first compelling analysis of what can be called a mechanical procedure and Kurt Gödel asserted that he found Turing's analysis "perfect."[3] In addition some other major areas of theoretical overlap between logic and computer science are:

  • Gödel's incompleteness theorem proves that any logical system powerful enough to characterize arithmetic will contain statements that can neither be proven true nor false within that system. This has direct application to theoretical issues relating to the feasibility of proving the completeness and correctness of software.[4]
  • The frame problem is a basic problem that must be overcome when using first-order logic to represent the goals and state of an artificial intelligence agent.[5]
  • The Curry-Howard correspondence is a relation between logical systems and software. This theory established a precise correspondence between proofs and programs. In particular it showed that terms in the simply-typed lambda-calculus correspond to proofs of intuitionistic propositional logic.
  • Category theory represents a view of mathematics that emphasizes the relations between structures. It is intimately tied to many aspects of computer science: type systems for programming languages, the theory of transition systems, models of programming languages and the theory of programming language semantics.[6]

Computers to assist logicians[edit]

One of the first applications to use the term Artificial Intelligence was the Logic Theorist system developed by Allen Newell, J.C. Shaw, and Herbert Simon in 1956. One of the things that a logician does is to take a set of statements in logic and deduce the conclusions (additional statements) that must be true by the laws of logic. For example, If given a logical system that states "All humans are mortal" and "Socrates is human" a valid conclusion is "Socrates is mortal". Of course this is a trivial example. In actual logical systems the statements can be numerous and complex. It was realized early on that this kind of analysis could be significantly aided by the use of computers. The Logic Theorist validated the theoretical work of Bertrand Russell and Alfred North Whitehead in their influential work on mathematical logic called Principia Mathematica. In addition, subsequent systems have been utilized by logicians to validate and discover new logical theorems and proofs.[7]

Logic applications for computers[edit]

There has always been a strong influence from mathematical logic on the field of Artificial Intelligence (AI). From the beginning of the field it was realized that technology to automate logical inferences could have great potential to solve problems and draw conclusions from facts. Ron Brachman has described first-order logic (FOL) as the metric by which all AI knowledge representation formalisms should be evaluated. There is no more general or powerful known method for describing and analyzing information than FOL. The reason FOL itself is simply not used as a computer language is that it is actually too expressive, in the sense that FOL can easily express statements that no computer, no matter how powerful, could ever solve. For this reason every form of knowledge representation is in some sense a trade off between expressivity and computability. The more expressive the language is, the closer it is to FOL, the more likely it is to be slower and prone to an infinite loop.[8]

For example, IF THEN rules used in Expert Systems are a very limited subset of FOL. Rather than arbitrary formulas with the full range of logical operators the starting point is simply what logicians refer to as Modus Ponens. As a result, the computability of rule based systems can be quite good, especially if they take advantage of optimization algorithms and compilation.[9]

Another major area of research for logical theory was software engineering. Research projects such as the Knowledge-Based Software Assistant and Programmer's Apprentice programs applied logical theory to validate the correctness of software specifications. They also used them to transform the specifications into efficient code on diverse platforms and to prove the equivalence between the implementation and the specification.[10] This formal transformation driven approach is often far more effort than traditional software development. However, in specific domains with appropriate formalisms and reusable templates the approach has proven viable for commercial products. The appropriate domains are usually those such as weapons systems, security systems, and real time financial systems where failure of the system has excessively high human or financial cost. An example of such a domain is Very Large Scale Integrated (VLSI) Design—the process for designing the chips used for the CPU's and other critical components of digital devices. An error in a chip is catastrophic. Unlike software chips can't be patched or updated. As a result, there is commercial justification for using formal methods to prove that the implementation corresponds to the specification.[11]

Another important application of logic to computer technology has been in the area of frame languages and automatic classifiers. Frame languages such as KL-ONE have a rigid semantics. Definitions in KL-ONE can be directly mapped to set theory and the predicate calculus. This allows specialized theorem provers called classifiers to analyze the various declarations between sets, subsets, and relations in a given model. In this way the model can be validated and any inconsistent definitions flagged. The classifier can also infer new information, for example define new sets based on existing information and change the definition of existing sets based on new data. The level of flexibility is ideal for handling the ever changing world of the Internet. Classifier technology is built on top of languages such as the Web Ontology Language to allow a logical semantic level on to the existing Internet. This layer of is called the Semantic web.[12][13]

Temporal logic is used for reasoning in concurrent systems.[14]

See also[edit]

References[edit]

  1. ^ Lewis, Harry R.; Christos H. Papadimitriou (1981). Elements of the Theory of Computation. Englewood Cliffs, New Jersey: Prentice-Hall. ISBN 0-13-273417-6. 
  2. ^ Davis, Martin. "Influences of Mathematical Logic on Computer Science". In Rolf Herken. The Universal Turing Machine. Springer Verlag. Retrieved 26 December 2013. 
  3. ^ Kennedy, Juliette. Interpreting Godel. Cambridge University Press. Retrieved 17 August 2015. 
  4. ^ Hofstadter, Douglas R. Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books. ISBN 978-0465026562. 
  5. ^ McCarthy, J; P.J. Hayes (1969). "Some philosophical problems from the standpoint of artificial intelligence". Machine Intelligence. 4: 463–502. 
  6. ^ Barr, Michael; Charles Wells (1990). Category Theory for Computer. Prentice-Hall. 
  7. ^ Newell, Allen; J.C. Shaw; H.C. Simon (1963). "Empirical explorations with the logic theory machine". In Ed Feigenbaum. Computers and Thought. McGraw Hill. pp. 109–133. ISBN 978-0262560924. 
  8. ^ Levesque, Hector; Ronald Brachman (1985). "A Fundamental Tradeoff in Knowledge Representation and Reasoning". In Ronald Brachman and Hector J. Levesque. Reading in Knowledge Representation. Morgan Kaufmann. p. 49. ISBN 0-934613-01-X. The good news in reducing KR service to theorem proving is that we now have a very clear, very specific notion of what the KR system should do; the bad new is that it is also clear that the services can not be provided... deciding whether or not a sentence in FOL is a theorem... is unsolvable. 
  9. ^ Forgy, Charles (1982). "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem*" (PDF). Artificial Intelligence. 19: 17–37. doi:10.1016/0004-3702(82)90020-0. Retrieved 25 December 2013. 
  10. ^ Rich, Charles; Richard C. Waters (November 1987). "The Programmer's Apprentice Project: A Research Overview" (PDF). IEE Expert Special Issue on the Interactions between Expert Systems and Software Engineering. Retrieved 26 December 2013. 
  11. ^ Stavridou, Victoria (1993). Formal Methods in Circuit Design. Press Syndicate of the University of Cambridge. ISBN 0-521-443369. Retrieved 26 December 2013. 
  12. ^ MacGregor, Robert (June 1991). "Using a description classifier to enhance knowledge representation". IEEE Expert. 6 (3): 41–46. doi:10.1109/64.87683. Retrieved 10 November 2013. 
  13. ^ Berners-Lee, Tim; James Hendler; Ora Lassila (May 17, 2001). "The Semantic Web A new form of Web content that is meaningful to computers will unleash a revolution of new possibilities". Scientific American. 284: 34–43. doi:10.1038/scientificamerican0501-34. Archived from the original on April 24, 2013. 
  14. ^ Colin Stirling (1992). "Modal and Temporal Logics". In S. Abramsky; D. M. Gabbay; T. S. E. Maibaum. Handbook of Logic in Computer Science. II. Oxford University Press. pp. 477–563. ISBN 0-19-853761-1. 

Further reading[edit]

External links[edit]

Disclaimer

None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Powered by YouTube
Wikipedia content is licensed under the GFDL and (CC) license