Fundamentals of Computer Science - Week 2 Summary - Part 2 out of 2

Predicates and Quantifiers

Introduction

Until now, propositional logic cannot adequately express the meaning of all statements in mathematics and in natural language. For example, suppose that we know that

"every computer connected to the university network is functioning properly"

No rules of propositional logic allow us to conclude the trutth of the statement

Predicates

Statements involving variables, such as "x > 3", "x = y + 3" and

"computer x is under attack by an intruder"

are often found in mathematical assertions. These statements are neither true nor false when the values of the variables are not specified. There are ways that propositions can be produced from such statements.

Consider

"x is greater than 3"

* has two parts
* x, is the subject of the statement
* "is greater than 3" refers to a property that the subject of the statement can have.
* "x is greater than 3" can be denoted by P(x) where P denotes the predicate "is greater than 3" and x is the variable. The statement P(x) is also said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.

Quantifiers

TODO p. 40 - ate 52

First-order logic

Important notions

* Predicates that describe properties of objects
  * Odd(3) means 3 is an odd number; Odd is a predicate, 3 is an object
  * Equal(5,6) means 5 and 6 are equal; Equal isa predicate, 5,6 are objects
* Predicates take arguments and become propositions
* The connectives for propositional logic apply the same way
  * Odd(3) OR Prime(3), which means 3 is odd and 3 is prime, true
  * Even(4) -> Prime(4), which means 4 is even then 4 is prime, false
* Quantifiers make reasoning on miltiple objects
* The objects for the quantified statements are choosen from a Domain

Quantifiers allow us to reason about multiple objects

* Existencial quantifier, denoted by Ǝ (mirroed E)
* Ǝx "some formula"
* Means for some x, the statement "some formula" is true
* Example: vx Odd(x) it means some numbers are odd
* Ǝx Prime(x) it means there exists at least one number that is primes
* If at least one element is true, then it's true

Quantifiers allow us to reason about multiple objects

* ∀ is called the universal quantifier
* ∀x "some formula"
* Means for ALL x, the statement "some formula" is true
* Example ∀x(Odd(x) v Even(x)); it means all numbers are either odd or even
* ∀x(x<x+1) it means all numbers
* Note, it is NOT enough to find some elements that make the formula true; it must be true for all elements

Quantifiers and connectives

* ƎxP(X) and domain D = { x1, x2, ..., xn) means P(x1) OR (Px2) OR ... (xn)
* ∀xP(X) and domain D = { x1, x2, ..., xn) means P(x1) AND (Px2) AND ... (xn)

Comments

Post a Comment

Popular posts from this blog

syllabus: Algorithms and Data Structures 1 [CM1035]

Algorithms and Data Structures 1 [CM1035] Course Description The study of algorithms and data structures is central to an undergraduate degree in computer science. This course will introduce you to your first algorithms and data structures, as well as the tools of abstraction required to help you decide which of these concepts to use. In this way you will not only enhance your box of problem solving tools, you will be able to critically compare, and assess the advantages and disadvantages, of these tools. The course starts at a basic level by describing problems and algorithms in computer science. It then goes on to introduce the tools for describing algorithms: flowcharts and pseudocode. You will then build on these basics to cover a wide range of topics: Abstract data structures such as vectors, queues and stacks. Implementation of abstract data structures with arrays and linked lists. Searching algorithms: Linear Search and Binary Search. Sorting algorithms: Bubble Sort,...
Read more

syllabus: Fundamentals of Computer Science [CM1025]

Course Description Target Audience - Those looking to explore the concepts that underpin modern computer science principles. Learners will begin to appreciate some of the core concepts that form the basis of modern computer systems, how they are designed and built and some of the challenges that they will face in developing their own systems. Content Differentiation - This course covers a variety of concepts, presenting them in a clear, accessible and reasoned way. Concepts are explained through examples and learning is reinforced through a variety of interactive activities. Course Goals and Objectives Upon successful completion of this module, you will be able to: Understand the core concepts that underpin modern computer science. Explain, describe and employ different techniques in both a theoretical and practical way. Appreciate how more complex techniques employ the fundamentals that are covered in this course. Textbook and Readings Specific essential readi...
Read more

Introduction to Programming - Week 1 and 2 Summary

Image
What is programming? Commands are the smallest building blocks of your program. A single intruction to the computer to perform an action. A program is a collection of these individual ccommands put together in the right order to solve a problem, complete a task, or maybe interact with the user. The collection of commands you write for your program is called source code. 2D coordinate system * Computer screens are made up of tiny dots * Each one of these dots is called pixels * In p5.js we create an area of pixels on a webpage we can draw to: this is called the canvas * A canvas needs a width and height in pixels How you will be assessed?  * New topic every two weeks * This is your first topic (development environment) * Each topic will be divided into a series of lessons * In a lesson you will learn by watching videos * The game keeps a running total of your score which increases as you progress but fixed grades are taken at two points in the term. Each of...
Read more