Anki Deck Changes

Note 1: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: .@%aS+kuV

modified

Before

Front

In any ring \(\langle R; +, -, 0, \cdot, 1 \rangle\), and for all \(a, b \in R\) \(a0 =\) \(0a = 0\).

Back

In any ring \(\langle R; +, -, 0, \cdot, 1 \rangle\), and for all \(a, b \in R\) \(a0 =\) \(0a = 0\).

The zero (neutral of additive group) pulls all other elements to 0 by multiplication.

\(0a=(0+0)a=0a+0a\) and thus \(0a - 0a = 0a \implies 0 = 0a\)

After

Front

In any ring \(\langle R; +, -, 0, \cdot, 1 \rangle\), and for all \(a, b \in R\) \(a0 =\) \(0a = 0\).

Back

In any ring \(\langle R; +, -, 0, \cdot, 1 \rangle\), and for all \(a, b \in R\) \(a0 =\) \(0a = 0\).

The zero (neutral of additive group) pulls all other elements to 0 by multiplication.

\(0a=(0-0)a=0a-0a=0\)

Field-by-field Comparison

Field	Before	After
Extra	The zero (neutral of additive group) pulls all other elements to 0 by multiplication.<br><br>\(0a=(0+0)a=0a~~+0a\) and thus \(0a - 0a = 0a \implies 0 = 0a~~\)	The zero (neutral of additive group) pulls all other elements to 0 by multiplication.<br><br>\(0a=(0-0)a=0a-0a=0\)

Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::1._Definition_of_a_Ring

Note 2: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: BTm~S%al=(

modified

Before

Front

The {{c1::set of statements \(\mathcal{S}\)}} is denoted as a subset of the finite bit strings \(\Sigma^*\).

Back

The {{c1::set of statements \(\mathcal{S}\)}} is denoted as a subset of the finite bit strings \(\Sigma^*\).

After

Front

The {{c1::set of statements \(\mathcal{S}\)}} is a subset of the finite bit strings \(\Sigma^*\).

Back

The {{c1::set of statements \(\mathcal{S}\)}} is a subset of the finite bit strings \(\Sigma^*\).

Field-by-field Comparison

Field	Before	After
Text	The {{c1::set of statements  \(\mathcal{S}\)}} is ~~denoted as~~ {{c2:: a subset of the finite bit strings  \(\Sigma^*\)}}.	The {{c1::set of statements  \(\mathcal{S}\)}} is {{c2:: a subset of the finite bit strings  \(\Sigma^*\)}}.

Tags: ETH::1._Semester::DiskMat::6._Logic::2._Proof_Systems::1._Definition

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: BYs?C)>Q^q

modified

Before

Front

A proof system is sound if no false statement has a proof: \(\phi(s, p) = 1 \implies \tau(s) = 1\).

Back

A proof system is sound if no false statement has a proof: \(\phi(s, p) = 1 \implies \tau(s) = 1\).

Note that the use of \(\implies\)is not the correct formalism.

For all \(s \in \mathcal{S}\) for which there exists a \(p \in \mathcal{P}\) with \(\phi(s, p) = 1\), we have \(\tau(s) = 1\) is the correct formal definition.

After

Front

A proof system is sound if no false statement has a proof: \(\phi(s, p) = 1 \implies \tau(s) = 1\).

Back

A proof system is sound if no false statement has a proof: \(\phi(s, p) = 1 \implies \tau(s) = 1\).

Note that the use of \(\implies\)is not the correct formalism.

For all \(s \in \mathcal{S}\) for which there exists a \(p \in \mathcal{P}\) with \(\phi(s, p) = 1\), we have \(\tau(s) = 1\) is the correct formal definition.

Field-by-field Comparison

Field	Before	After
Text	A proof system is {{c2::~~ ~~<b>sound</b>}} if {{c1:: no false statement has a proof: \(\phi(s, p) = 1 \implies \tau(s) = 1\)}}.	A proof system is {{c2::<b>sound</b>}} if {{c1:: no false statement has a proof: \(\phi(s, p) = 1 \implies \tau(s) = 1\)}}.

Tags: ETH::1._Semester::DiskMat::6._Logic::2._Proof_Systems::1._Definition

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: Byvb`08=9%

modified

Before

Front

A partial function \(A \to B\) is a relation from \(A\) to \(B\) such that{{c1::\(\forall a \in A \; \forall b,b' \in B \; (a \mathop{f} b \land a\mathop{f} b' \to b = b')\) (well-defined).}}

Back

A partial function \(A \to B\) is a relation from \(A\) to \(B\) such that{{c1::\(\forall a \in A \; \forall b,b' \in B \; (a \mathop{f} b \land a\mathop{f} b' \to b = b')\) (well-defined).}}

After

Front

A partial function \(A \to B\) is a relation from \(A\) to \(B\) such that {{c1::\(\forall a \in A \; \forall b,b' \in B \; (a \mathop{f} b \land a\mathop{f} b' \to b = b')\) (well-defined).}}

Back

A partial function \(A \to B\) is a relation from \(A\) to \(B\) such that {{c1::\(\forall a \in A \; \forall b,b' \in B \; (a \mathop{f} b \land a\mathop{f} b' \to b = b')\) (well-defined).}}

Field-by-field Comparison

Field	Before	After
Text	A <b>partial function </b>\(A \to B\) is a relation from \(A\) to \(B\) such that{{c1::\(\forall a \in A \; \forall b,b' \in B \; (a \mathop{f} b \land a\mathop{f} b' \to b = b')\) (well-defined).}}	A <b>partial function </b>\(A \to B\) is a relation from \(A\) to \(B\) such that {{c1::\(\forall a \in A \; \forall b,b' \in B \; (a \mathop{f} b \land a\mathop{f} b' \to b = b')\) (well-defined).}}

Tags: ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::6._Functions

Note 5: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: G3,dI)){d{

modified

Before

Front

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

Back

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

\(\mathbb{Z}_n\) is generated by all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\) (all elements coprime to \(n\)).

Proof idea:
- If \(\mathbb{Z}_n = \langle a \rangle\), then \(1 \in \langle a \rangle\)
- This means \(au \equiv_n 1\) for some \(u\)
- By Bézout's identity, this implies \(\gcd(a, n) = 1\) (since \(\gcd\) must divide both \(au-qn\) and 1).

After

Front

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

Back

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

\(\mathbb{Z}_n\) is generated by all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\) (all elements coprime to \(n\)).

Proof:

\(a\) generator \(\implies\)\(\gcd(a, n) = 1\)
\(\mathbb{Z}_n = \langle a \rangle\)
\(\implies\)\(1 \in \langle a \rangle\)
\(\implies\)\(a^u = ua \equiv_n 1\) for some \(u\)
\(\implies\)\(\gcd(a, n) = 1\) (\(\gcd\) must divide both \(au-qn\) and 1).

\(\gcd(a, n) = 1 \implies\)\(a\) generator
\(\gcd(a, n) = 1\)
\(\implies\)\(ua + un = 1\) for some \(u, n\) (Bézout)
\(\implies\)\(ua = a^u \equiv_n 1\)
\(\implies\)for every element \(b\), \(\exists c\) s.t. \(b = c \cdot u \cdot a = (a^u)^c = a^{u \cdot c}\)

Field-by-field Comparison

Field	Before	After
Back	<p>\(\mathbb{Z}_n\) is generated by <strong>all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\)</strong> (all elements coprime to \(n\)).</p> <p><strong>Proof ~~idea~~</strong>~~:<br> - If~~ \(\mathbb{Z}_n = \langle a \rangle\)~~, then~~ \(1 \in \langle a \rangle\)<br> ~~- This means \(au~~ \equiv_n 1\) for some \(u\)<br> ~~- By Bézout's identity, this~~ implies \(\gcd(a, n) = 1\) (~~since ~~\(\gcd\) must divide both \(au-qn\) and 1).</p>	<p>\(\mathbb{Z}_n\) is generated by <strong>all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\)</strong> (all elements coprime to \(n\)).</p> <p><strong>Proof:</strong></p><p>\(a\) generator \(\implies\)\(\gcd(a, n) = 1\)<br>\(\mathbb{Z}_n = \langle a \rangle\)<br>\(\implies\)\(1 \in \langle a \rangle\)<br>\(\implies\)\(a^u = ua \equiv_n 1\) for some \(u\)<br>\(\implies\)\(\gcd(a, n) = 1\) (\(\gcd\) must divide both \(au-qn\) and 1).</p>\(\gcd(a, n) = 1 \implies\)\(a\) generator<br>\(\gcd(a, n) = 1\)<br>\(\implies\)\(ua + un = 1\) for some \(u, n\) (Bézout)<br>\(\implies\)\(ua = a^u \equiv_n 1\)<br>\(\implies\)for every element \(b\), \(\exists c\) s.t. \(b = c \cdot u \cdot a = (a^u)^c = a^{u \cdot c}\)

Tags: ETH::1._Semester::DiskMat::5._Algebra::3._The_Structure_of_Groups::5._Cyclic_Groups

Note 6: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: Pj6Xy8Kn7N

modified

Before

Front

The resolution calculus is sound, i.e. if {{c2::\(\mathcal{K} \vdash_{\textbf{Res}} K\)}}, then {{c2::\(\mathcal{K} \models K\)}}.

Back

The resolution calculus is sound, i.e. if {{c2::\(\mathcal{K} \vdash_{\textbf{Res}} K\)}}, then {{c2::\(\mathcal{K} \models K\)}}.

After

Front

The resolution calculus is sound, i.e. if {{c2::\(\mathcal{K} \vdash_{Res} K\)}}, then {{c2::\(\mathcal{K} \models K\)}}.

Back

The resolution calculus is sound, i.e. if {{c2::\(\mathcal{K} \vdash_{Res} K\)}}, then {{c2::\(\mathcal{K} \models K\)}}.

Field-by-field Comparison

Field	Before	After
Text	The resolution calculus is {{c1::<i>sound</i>}}, i.e. if {{c2::\(\mathcal{K} \vdash_{~~\textbf{~~Res}} K\)}}, then {{c2::\(\mathcal{K} \models K\)}}.	The resolution calculus is {{c1::<i>sound</i>}}, i.e. if {{c2::\(\mathcal{K} \vdash_{Res} K\)}}, then {{c2::\(\mathcal{K} \models K\)}}.

Tags: ETH::1._Semester::DiskMat::6._Logic::5._Propositional_Logic::5._The_Resolution_Calculus_for_Propositional_Logic

Note 7: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: Qn4Vs7Ck2H

modified

Before

Front

An interpretation consists of {{c1::a set \(\mathcal{Z} \subseteq \Lambda\) of \(\Lambda\)}}, {{c2::a domain (a set of possible values) for each symbol in \(\mathcal{Z}\)}}, and {{c3::a function that assigns to each symbol in \(\mathcal{Z}\) a value in the associated domain}}.

Back

An interpretation consists of {{c1::a set \(\mathcal{Z} \subseteq \Lambda\) of \(\Lambda\)}}, {{c2::a domain (a set of possible values) for each symbol in \(\mathcal{Z}\)}}, and {{c3::a function that assigns to each symbol in \(\mathcal{Z}\) a value in the associated domain}}.

Often the domain is defined in terms of the universe \(U\) where a symbol can be a function, predicate or element of \(U\).

A set of symbols \(\mathcal{Z} \subseteq \Lambda\)
- \(\Lambda\) is the "alphabet" or collection of all available symbols
- \(\mathcal{Z}\) is the subset of symbols we're actually interpreting
A domain for each symbol
- For each symbol in \(\mathcal{Z}\), there's a set of possible values it could take
- This is the "universe of discourse" for that symbol
An assignment function
- For each symbol in \(\mathcal{Z}\), the function picks one specific value from its domain
- This gives meaning to each symbol

After

Front

An interpretation consists of {{c1::a set \(\mathcal{Z} \subseteq \Lambda\) of \(\Lambda\)}}, {{c2::a domain (a set of possible values) for each symbol in \(\mathcal{Z}\)}}, and {{c3::a function that assigns to each symbol in \(\mathcal{Z}\) a value in the associated domain}}.

Back

An interpretation consists of {{c1::a set \(\mathcal{Z} \subseteq \Lambda\) of \(\Lambda\)}}, {{c2::a domain (a set of possible values) for each symbol in \(\mathcal{Z}\)}}, and {{c3::a function that assigns to each symbol in \(\mathcal{Z}\) a value in the associated domain}}.

A set of symbols \(\mathcal{Z} \subseteq \Lambda\)
- \(\Lambda\) is the "alphabet" or collection of all available symbols
- \(\mathcal{Z}\) is the subset of symbols we're actually interpreting
A domain for each symbol
- For each symbol in \(\mathcal{Z}\), there's a set of possible values it could take
- Often the domain is defined in terms of the universe \(U\) where a symbol can be a function, predicate or element of \(U\).
An assignment function
- For each symbol in \(\mathcal{Z}\), the function picks one specific value from its domain
- This gives meaning to each symbol

Field-by-field Comparison

Field	Before	After
Text	An <i>interpretation</i> consists of {{c1::a set \(\mathcal{Z} \subseteq \Lambda\) of \(\Lambda\)}}, {{c2::a domain (a set of possible values) for each symbol in \(\mathcal{Z}\)}}, and {{c3::a function that assigns to each symbol in \(\mathcal{Z}\) a value in the associated domain}}.	An <i>interpretation</i> consists of {{c1::a set \(\mathcal{Z} \subseteq \Lambda\) of \(\Lambda\)}}, {{c2::a domain (a set of possible values) for each symbol in \(\mathcal{Z}\)}}, and {{c3::a function that assigns to each symbol in \(\mathcal{Z}\) a value in the associated domain}}.
Extra	~~Often the domain is defined in terms of the <i>universe</i> \(U\) where a symbol can be a function, predicate or element of \(U\).<br>~~<ol><li><strong>A set of symbols</strong> \(\mathcal{Z} \subseteq \Lambda\)<ul> <li>\(\Lambda\) is the "alphabet" or collection of all available symbols </li> <li>\(\mathcal{Z}\) is the subset of symbols we're actually interpreting </li> </ul> </li> <li><strong>A domain for each symbol</strong> <ul> <li>For each symbol in \(\mathcal{Z}\), there's a set of possible values it could take </li> <li>~~This is the "universe of discourse" for that symbol~~</li> </ul> </li> <li><strong>An assignment function</strong> <ul> <li>For each symbol in \(\mathcal{Z}\), the function picks one specific value from its domain </li> <li>This gives meaning to each symbol</li> </ul> </li> <h2></h2></ol>	<ol><li><strong>A set of symbols</strong> \(\mathcal{Z} \subseteq \Lambda\)<ul> <li>\(\Lambda\) is the "alphabet" or collection of all available symbols </li> <li>\(\mathcal{Z}\) is the subset of symbols we're actually interpreting </li> </ul> </li> <li><strong>A domain for each symbol</strong> <ul> <li>For each symbol in \(\mathcal{Z}\), there's a set of possible values it could take </li> <li>Often the domain is defined in terms of the <i>universe</i> \(U\) where a symbol can be a function, predicate or element of \(U\).<br><ol></ol></li> </ul> </li> <li><strong>An assignment function</strong> <ul> <li>For each symbol in \(\mathcal{Z}\), the function picks one specific value from its domain </li> <li>This gives meaning to each symbol</li> </ul> </li> <h2></h2></ol>

Tags: ETH::1._Semester::DiskMat::6._Logic::3._Elementary_General_Concepts_in_Logic::3._Semantics::Interpretation

Note 8: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: Sm8Xz2Vn4Q

modified

Before

Front

How do you construct a CNF formula from a truth table?

Back

How do you construct a CNF formula from a truth table?

For every row evaluating to 0:
1. Take the disjunction of \(n\) literals
2. If \(A_i = 0\) in the row, take \(A_i\)
3. If \(A_i = 1\) in the row, take \(\lnot A_i\)
4. Then take the conjunction of all these rows

This works because \(F\) is \(0\) exactly if every single disjunction is true, which is the case by construction.

After

Front

How do you construct a CNF formula from a truth table?

Back

How do you construct a CNF formula from a truth table?

For every row evaluating to 0:
1. Take the disjunction of \(n\) literals
2. If \(A_i = 0\) in the row, take \(A_i\)
3. If \(A_i = 1\) in the row, take \(\lnot A_i\)
4. Then take the conjunction of all these rows

This works because \(F\) is \(0\) exactly if every single disjunction is true, which is the case by construction.

---

\(F\) should evaluate to true if we don't have the first zero row, not the second zero row, and so on. De Morgan flips the conjunction of the literals to a disjunction and adds the negation.

Field-by-field Comparison

Field	Before	After
Back	For every row evaluating to <b>0</b>:<br>1. Take the <i>disjunction</i> of \(n\) literals<br>2. If \(A_i = 0\) in the row, take \(A_i\)<br>3. If \(A_i = 1\) in the row, take \(\lnot A_i\)<br>4. Then take the <i>conjunction</i> of all these rows<br><br>This works because \(F\) is \(0\) exactly if every single disjunction is true, which is the case by construction.	For every row evaluating to <b>0</b>:<br>1. Take the <i>disjunction</i> of \(n\) literals<br>2. If \(A_i = 0\) in the row, take \(A_i\)<br>3. If \(A_i = 1\) in the row, take \(\lnot A_i\)<br>4. Then take the <i>conjunction</i> of all these rows<br><br>This works because \(F\) is \(0\) exactly if every single disjunction is true, which is the case by construction.<br><br>---<br><br>\(F\) should evaluate to true if we don't have the first zero row, not the second zero row, and so on. De Morgan flips the conjunction of the literals to a disjunction and adds the negation.

Tags: ETH::1._Semester::DiskMat::6._Logic::5._Propositional_Logic::4._Normal_Forms MEANINGFUL_DUPLICATE

Note 9: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: Up7Wv9Kn2S

modified

Before

Front

Propositional logic is (in relation to predicate logic):

Back

Propositional logic is (in relation to predicate logic):

embedded into predicate logic as a special case.
We extend it by the concept of predicates.

After

Front

Propositional logic is (in relation to predicate logic):

Back

Propositional logic is (in relation to predicate logic):

embedded into predicate logic as a special case.
We extend it by the concept of predicates.

Predicates of the form \(P()\) act as propositional symbols.

Field-by-field Comparison

Field	Before	After
Back	<i>embedded</i> into predicate logic as a <i>special case</i>. <br>We extend it by the concept of <b>predicates</b>.	<i>embedded</i> into predicate logic as a <i>special case</i>. <br>We extend it by the concept of <b>predicates</b>.<br><br>Predicates of the form \(P()\) act as propositional symbols.

Tags: ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::1._Syntax

Note 10: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: Yv3Tn8Zw5C

modified

Before

Front

The semantics of a logic defines a function \(\sigma\) {{c1::assigning to each formula \(F\) and each interpretation \(\mathcal{A}\) suitable for \(F\) a truth value\(\sigma(F, \mathcal{A})\)in \(\{0, 1\}\)}}.

Back

The semantics of a logic defines a function \(\sigma\) {{c1::assigning to each formula \(F\) and each interpretation \(\mathcal{A}\) suitable for \(F\) a truth value\(\sigma(F, \mathcal{A})\)in \(\{0, 1\}\)}}.

After

Front

The semantics of a logic defines a function \(\sigma\) {{c1::assigning to each formula \(F\) and each interpretation \(\mathcal{A}\) suitable for \(F\) a truth value \(\sigma(F, \mathcal{A})\) in \(\{0, 1\}\)}}.

Back

The semantics of a logic defines a function \(\sigma\) {{c1::assigning to each formula \(F\) and each interpretation \(\mathcal{A}\) suitable for \(F\) a truth value \(\sigma(F, \mathcal{A})\) in \(\{0, 1\}\)}}.

Field-by-field Comparison

Field	Before	After
Text	The <i>semantics</i> of a logic defines a function \(\sigma\) {{c1::assigning to each formula \(F\) and each interpretation \(\mathcal{A}\) suitable for \(F\) a truth value\(\sigma(F, \mathcal{A})\)in \(\{0, 1\}\)}}.	The <i>semantics</i> of a logic defines a function \(\sigma\) {{c1::assigning to each formula \(F\) and each interpretation \(\mathcal{A}\) suitable for \(F\) a truth value \(\sigma(F, \mathcal{A})\) in \(\{0, 1\}\)}}.

Tags: ETH::1._Semester::DiskMat::6._Logic::3._Elementary_General_Concepts_in_Logic::3._Semantics::Interpretation