MIT computer science 1.4.1~ 1.4.4

lec 1.4.1 Propositional Operators

제안 연산자

 

A proposition is either True or False.

제안은 참 또는 거짓입니다. 

 

Example:

There are 5 regular solids.

True

There are 6 regular solids.

False

 

Non-examples:

Wake up!

Where am I?

It's 3PM.

 

Copper 구리

Bronze 청동

 

Definition of OR

The value of (P OR Q) is T is T iff P is T, of Q is T, or Both are T.

F iff both P,Q are F 모두가 F인 경우 거짓이다

iff = If and only if 양쪽 모두 참이거나 거짓

 

Definition of XOR

The value of  (P XOR Q) is T iff exactly one of P and Q is T.

 

Definition of AND

The value of (P AND Q) is T iff both P and Q are T.

 

Definition of NOT

The value of NOT(P) is T iff the value of P is F.

혼선을 방지하기 위해 평범한 단어 표기법을 쓴다. 하지만 알아는 둬야 한다고 한다.

 

lec 1.4.3 Digital Logic

Logic 논리

반가산기는 두개의 입력이 있고

전가산기는 세개의 입력이 있다. a, b, carry

 

 

lec 1.4.4 Truth Tables(https://www.youtube.com/watch?v=_3WDzxt5p8c&list=PLUl4u3cNGP60UlabZBeeqOuoLuj_KNphQ&index=11)

진리표

 

Truth Assignments

진실 할당

A truth assignment assigns a value T of F to each propositional variable.

진실 지정은 각 명제 변수에 F의 값 T를 할당한다.

Computer scientists call assignment of values to variables an environment.

컴퓨터 과학자들은 환경변화에 대한 가치 배정을 부른다.

If we know the environment, we can find the value of a propositional formula.

만약 우리가 환경을 안다면, 우리는 명제 공식의 가치를 찾을 수 있다.

Equivalence

동등성

 

Two propositional formulas are equivalent iff they have the same truth value in all environments.

두가지 명제 공식에서 rators

 

제안 연산자

 

 

 

A proposition is either True or False.

 

제안은 참 또는 거짓입니다. 

 

 

 

Example:

 

There are 5 regular solids.

 

True

 

There are 6 regular solids.

 

False

 

 

 

Non-examples:

 

Wake up!

 

Where am I?

 

It's 3PM.

 

 

 

Copper 구리

 

Bronze 청동

 

 

 

Definition of OR

 

The value of (P OR Q) is T is T iff P is T, of Q is T, or Both are T.

 

F iff both P,Q are F 모두가 F인 경우 거짓이다

 

iff = If and only if 양쪽 모두 참이거나 거짓

 

 

 

Definition of XOR

 

The value of (P XOR Q) is T iff exactly one of P and Q is T.

 

 

 

Definition of AND

 

The value of (P AND Q) is T iff both P and Q are T.

 

 

 

Definition of NOT

 

The value of NOT(P) is T iff the value of P is F.

 



혼선을 방지하기 위해 평범한 단어 표기법을 쓴다. 하지만 알아는 둬야 한다고 한다.

 

 

 

lec 1.4.3 Digital Logic

 

Logic 논리

 



반가산기는 두개의 입력이 있고

 

전가산기는 세개의 입력이 있다. a, b, carry

 

 

 





 

 

lec 1.4.4 Truth Tables(https://www.youtube.com/watch?v=_3WDzxt5p8c&list=PLUl4u3cNGP60UlabZBeeqOuoLuj_KNphQ&index=11)

 

진리표

 

 

 

Truth Assignments

 

진실 할당

 

A truth assignment assigns a value T of F to each propositional variable.

 

진실 지정은 각 명제 변수에 F의 값 T를 할당한다.

 

Computer scientists call assignment of values to variables an environment.

 

컴퓨터 과학자들은 환경변화에 대한 가치 배정을 부른다.

 

If we know the environment, we can find the value of a propositional formula.

 

만약 우리가 환경을 안다면, 우리는 명제 공식의 가치를 찾을 수 있다.

 

 

Equivalence

 

동등성

 

 

Two propositional formulas are equivalent iff they have the same truth value in all environments.

 

두가지 명제 공식에서 만약 그것들이 모든 환경에서 동일한 진실 환경을 가진다면 동등하다.

 

 

Definition of IFF

If and only If

The value of (P IFF Q) is T iff P and Q have the same truth value.

 

Satisfiability & Validity

만족과 타당성

 

A formula is satisfiable iff it is true in some environment.

tutology in math

statement that is always true.

 

공식이 맞는지 알고싶다면 진리표를 확인하면 된다. 하지만 변수가 많아질수록 그 수는 너무 많아지기 때문에 힘들다.

 

Fast Test for SAT?

 

The P=NP? questions is equivalent to asking if there is an "efficient"(polynomial rather than exponential time) procedure to check satisfiability(SAT).

P=NP 질문은 효율적 절차가 있는지 묻는것과 같다.

 

polynomial rather than exponential time

지수시간이 아닌 다항식

 

SAT versus VALID

To check that G is valid, can check that NOT(G) is not satisfiable.

So checking for one is equally difficult(or easy) as checking for the other.

G가 유효한지 확인할려면 NOT(G)를 확인하면 된다.