SCC121: weeks 1-5 Flashcards by Madeleine Smith

Define a set

-A collection of objects/elements/members
-no duplicate values
-unordered

How well did you know this?

Not at all

Perfectly

Describe the function of the UNION operation

Values of two given sets are combined into another set, any duplicates are removed

How well did you know this?

Not at all

Perfectly

Describe the function of the INTERSECTION operation

Values that are found in BOTH given sets are combined to form a single set.

How well did you know this?

Not at all

Perfectly

Describe the concept of a cartesian product

The set of all possible ordered pairs, where the first component is a member of the first of two given sets, and the second component is of the second set.

How well did you know this?

Not at all

Perfectly

Describe an empty set

A set that contains no elements, the container still exists

How well did you know this?

Not at all

Perfectly

What are disjoint sets?

2 or more sets with no elements in common
Two sets where the intersection is an empty set

How well did you know this?

Not at all

Perfectly

Describe the difference between a proper subset and a subset

A proper subset is not equal to the super set

How well did you know this?

Not at all

Perfectly

What is the difference between a superset and a proper superset?

The superset cannot be equal to the subset

How well did you know this?

Not at all

Perfectly

Define a universal set

A non empty set of all possible elements relevant to the solution of a specific problem.

How well did you know this?

Not at all

Perfectly

Define a complement set

A complement set is the difference between a universal set and a subset of the universal set.

How well did you know this?

Not at all

Perfectly

Define a binary relation

A relation between two distinct sets.
A set of ordered pairs, a subset of the cartesian product

How well did you know this?

Not at all

Perfectly

what is the cardinality of a set?

Number of elements contained within a set. when a set contains subsets, the elements of the subset are not counted, only the subset itself

How well did you know this?

Not at all

Perfectly

what is an ordered pair?

a pair of objects with an order associated to them

How well did you know this?

Not at all

Perfectly

what is a cartesian product?

the set of all possible ordered pairs between two sets.

How well did you know this?

Not at all

Perfectly

what is an ordered n tuple?

same concept as an ordered pair, only containing n elements instead of two

How well did you know this?

Not at all

Perfectly

what values constitute the cartesian product of n sets?

a set of ordered n tuples.

How well did you know this?

Not at all

Perfectly

describe an n-ary relation.

a relation defined across n sets, described as a set of n tuples. a subset of the cartesian product of n sets.

How well did you know this?

Not at all

Perfectly

what is a subrelation?

same concept as subsets, only a relation whose every element can be found within a different relation, where the two relations are not equal.

How well did you know this?

Not at all

Perfectly

list the properties of relations:

-symmetry
-transitivity
-reflexivity
-irreflexivity
-equivalence

How well did you know this?

Not at all

Perfectly

what is the concept of the property symmetry in relation to relations?

for any ordered pair <a,b> in a relation, <b,a> can also be found in the relation.

How well did you know this?

Not at all

Perfectly

what is the concept of the property transitivity in relation to relations?

for the two ordered pairs <a,b>,<b,c> in a relation, the ordered pair <a,c> must be an element in the relation for the relation to be considered transitive.

How well did you know this?

Not at all

Perfectly

what is the concept of reflexivity in relation to relations?

every element of the set on which the relation is defined should be in a relation with itself. eg. for element ‘a’, <a,a> must be an element of the relation set.

How well did you know this?

Not at all

Perfectly

what is the concept of irreflexivity in relation to relations?

no element of the set on which the relation is defined can be in a relation with itself. eg. for element ‘a’, <a,a> CANNOT be an element of the relation set.

How well did you know this?

Not at all

Perfectly

what is the concept of equivalence in relation to relations?

a relation is an equivalence relation if the relation is reflexive, symmetric and transitive.

How well did you know this?

Not at all

Perfectly

define a function

a 'machine' which, given an input, produces a unique output -output value depends in some way on the input value

list some methods of displaying functions

-table -formula -graph

What are the two main rules used to define functions?

-inputs must only map to one output -every input must map to an output

define the domain and codomain

where f: A--->B -A = domain: the set of all possible inputs -B = codomain: the set of all possible outputs

define the range of a function

the set of values actually output by the function

what is the difference between the range and codomain?

the codomain is the set of all possible outputs, whereas the range is the set of values that are actually output by a function.

define the image and preimage of a function.

preimage = input image = output

define a bijective function

a function that is both injective and surjective A maps to B perfectly

what is meant by the term surjective? (referring to a function)

the range of the function must be equal to the codomain. -where f: A--->B, there can be no values of B that aren't mapped to by a value of A -every B has some A

what is meant by the term injective? (referring to functions)

for every image, there must only be one unique preimage. -where f: A-->B, no two values of A can map to the same value of B - B cannot have many A

describe the concept of a proposition

a claim/statement that is either True or False. Truth value is used to indicate state of a proposition

what is an atomic proposition?

a proposition whose outcome doesn't depend on another proposition

what is a compound proposition?

a proposition constructed of atomic propositions combined using fundamental connectives

what are fundamental connectives?

-AND -OR -XOR -NOT -Conditional -Biconditional

what is the name for a proposition formed with an AND connective?

conjunction

what is the name for a proposition formed with an OR connective?

disjunction

what is the name of a proposition formed by a XOR connective?

exclusive conjunction

what is the name of a proposition formed with a NOT connective?

negation

what are the components of a proposition formed with a CONDITIONAL connective? (if....then)

antecedent and consequent---> IF antecedent THEN consequent

describe a proposition containing BICONDITIONAL connective

constructed with an "if and only if" statement

how is the proposition of the connective "P AND Q" written?

P^Q

how is the proposition of the connective "P OR Q" written?

P v Q

how is the proposition of the connective "P XOR Q" written?

P ⊕ Q

how should the proposition "NOT P" be written?

what is the condition for an AND proposition to be true?

each connected proposition must be true.

what is the condition for an OR proposition to be false?

each connected proposition must be false. If any connected proposition is true, the whole proposition is true

what are the conditions for a XOR proposition to be true?

an odd number of the connected propositions must be true for the whole proposition to be true

what are the conditions for a biconditional proposition to be true?

when each connected proposition has the same truth value.

what is a tautology?

a proposition which is always true, regardless of its atomic propositions.

what is a contradiction?

propositions that are always false regardless of their atomic propositions

what is a contingency?

propositions that are neither tautologies nor contradictions

what is logical equivalency?

two propositions can be logically equivalent if they have the same truth values under the same conditions

what is an argument?

a sequence of propositions that end in a conclusion

what is a premise

the basis on which we establish the conclusion

how are arguments written?

Premise 1 Premise 2 Premise n ---------------- therefore (dot dot dot) conclusion

what are inference rules?

templates for evaluating the validity of arguments

what are replacement rules?

rules for replacing parts of proposition with logically equivalent expression

describe the concept of modus ponens

structured around a conditional- "if it is raining, it is cloudy" it is raining, therefore it is cloudy.

describe the concept of modus tollens

a negated modus ponens: "if it is raining, it is cloudy"- it is not cloudy, therefore it is not raining

explain the concept of hypothetical syllogism

essentially linking multiple arguments by using implication. "if it is raining it will be cloudy" "if it is cloudy i will be sad" "if it is raining ----> i will be sad"

what is the point of replacement rules?

if two arguments are logically equivalent, they can be switched

commutative rule:

P v Q = QvP AND P ^Q = Q^P

Associative rule:

the grouping of propositions does not affect the result of conjunction/disjunction

what is the distributive rule?

P^(QvR) = (P^Q) v (P^R)

what is de morgan's replacement rule?

~P^~Q = ~(PvQ) ~Pv~Q = ~(P^Q)

what is the absorption rule?

P v (P^Q) = P P ^ (PvQ) = P

what are the identity rules?

P ^T = P ----> where T is a tautology Pv F = P ----->where F is a contradiction

what is the idempotence rule?

P^P = P PvP =P

what are the negation rules?

Pv~P= tautology P^~P = contradiction

what is the implication rule?

P---> Q = ~PvQ

what is the contraposition rule?

P--->Q = ~Q--->~P

what is the equivalence rule?

P<--> = (P--->Q)v (

what is disjunctive syllogism?

a sort of negation by using implication. "i will choose soup or salad" i didn't choose soup, therefore i chose salad.

describe some limits of propositional logic

- parts of propositions are undescribed -links between parts of propositions -statements like "for all", "for some" not covered ----> predicate logic allows propositions to be picked apart.

why is predicate logic necessary?

accounts for links between prepositions and qualifiers

describe the syntax of predicate logic

- terms- similar to subjects/objects -predicates- properties/relations -operators- connectors/quantifiers

what are the types of predicate logic?

-properties: typically 1 term -relationships: typically 2+ terms

what are atomic formulae?

consist of one predicate + one or more terms

SCC121: weeks 1-5 Flashcards

discrete maths and logic (94 cards)