Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am faced with this task:

"Let M be the set of all valuations. Let for each propositional formula $A: [A] = v \in M : v(A) = 1$. Show that:

$[A \land B] = [A] \cap [B]$

So, I get the idea what I'm supposed to prove, but the definitions escape me. I would like to know if

1) Does "Let M be the set of all valuations" mean that $M = \{0,1\}$ ?

2) What do the square brackets mean in logic? I suppose they are not matrices nor intervals.

2) How exactly am I supposed to read the $A: [A] = v \in M : v(A) = 1$ in English?

I understand that I'm supposed to show that when A is true and represented as a set $\{1\}$ it's intersection with B gives similar truth table to the boolean AND operator ( $\{1\}\cap \{1\} = \{1\}$ and $\{1\} \cap \{0\} = \emptyset$. I'm not just yet getting there formally.

Any help in understanding the mathematical language is appreciated!

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Suppose that our language has a certain collection of basic proposition letters. That set can be finite or infinite. But for simplicity let this set be finite, and (say) suppose that it consists of the letters $P_1,P_2,\dots,P_n$.

A valuation is an assignment of (truth) values to each of the proposition letters. Each value is $1$ or $0$ (or alternately T and F, there are plenty of other notations, but your course seems to use $1$ for true and $0$ for false).

Take such a valuation $v$. The valuation $v$ can be extended to all sentences of the language in the natural way. For example, if $P$ is a proposition letter, then we say that $v(\lnot P)=0$ if $v(P)=1$, and that $v(\lnot P)=1$ if $v(P)=0$. Here $\lnot$ is the logical "not": the notation in your course may be different. We continue to extend $v$ by saying what $v(X)$ is for more and more complex sentences. Since all sentences can be built up, starting from proposition letters, by using basic logical operations, it is enough to say what $v(\lnot A)$ is, if we know what $v(A)$ is, what $v(A\land B)$ is, if we know $v(A)$ and $v(B)$, and so on for the other logical operations.

For your problem, we review how one extends $v$ to $v(A\land B)$. By definition, $v(A\land B)=1$ if $v(A)$ and $v(B)$ are both equal to $1$, and $v(A\land B)=0$ otherwise. This captures the intuitive idea that $A\land B$ is true precisely if both $A$ and $B$ are true.

Let $A$ be a sentence. Your course uses the notation $[A]$ for the set of all valuations $v$ such that $v(A)=1$. In symbols, $$[A]=\{v\in M: v(A)=1\}.$$

That notation is specific to your course. There is no really standard notation for the concept. Square brackets are used in various other ways in mathematics. There is no connection with intervals, or matrices. The instructor, or textbook writer, just wanted a convenient abbreviation.

Suppose, for example, that the valuation $v$ assigns value $1$ to $P_1$, value $1$ to $P_2$, and value $0$ to $P_3$. Then $v(P_1\land P_2)=1$, so if $A=p_1\land P_2)$, then $v(A)=1$, so $v\in [A]$. Similarly, $v(P_1\land P_3)=0$, so if $A=P_1\land P_3$, the $v\notin [A]$.

Informally, $[A]$ is the set of all valuations that make $A$ true. It is the collection of ways to assign truth/falsehood to the various proposition letters so that $A$ ends up being true.

Here is another example. Let $A$ be the sentence $P_1\lor \lnot P_1$. Whatever value we assign to the basic proposition letters $P_i$, the sentence $P_1\lor \lnot P_1$ will be true, so every valuation $v$ is an element of $[A]$. This is a fancy way of saying that $A$ is a tautology.

Finally, we get to the specific problem! You are asked to show that $$[A \land B] = [A] \cap [B].$$ Note that by definition, the left-hand side is a set, and the right-hand side is a set. We typically show that two sets $X$ and $Y$ are equal by showing that anything in $X$ is also in $Y$, and that anything in $Y$ is also in $X$. So there are two things that need to be shown. Sometimes they can be handled together, but it is safer to deal with them separately.

(i) We first show that if $v$ is in $[A \land B]$, then $v$ is in $[A] \cap [B]$. So suppose that $v$ is in $[A \land B]$. Then by definition, $v(A \land B)=1$. But by definition, this forces $v(A)=1$ and $v(B)=1$. Since $v(A)=1$, we have $v\in [A]$. Similarly, $v\in [B]$. So $v$ is in both $[A]$ and $[B]$, and therefore $v\in [A] \cap [B]$. With fewer symbols, because $v$ makes $A\land B$ true, it makes $A$ true, and also makes $B$ true, so $v$ in the intersection of $[A]$ and $[B]$.

(ii) We next show that if $v$ is in $[A] \cap [B]$, then $v$ is in $[A \land B]$. So suppose that $v$ is in $[A] \cap [B]$. Then $v\in [A]$ and $v\in [B]$. So $v(A)=1$ and $v(B)=1$. So $v(A\land B)=1$. So $v\in [A\land B]$.

Remark: I hope that you will see that once we figured out what we needed to show, actually showing it turned out to be pretty easy. The exercise you were given is basically a language lesson, much like being asked to use French irregular verbs in a sentence after learning about the basic grammar.

share|improve this answer
    
Thank you! This was exactly what I needed to understand the definition! The study material was very vague on this subject and I couldn't find anywhere a clear definition of the square brackets in this context. –  Remolod Domelor Feb 22 '12 at 19:37

A valuation is a truth assignment to all propositions. All valuations are all possible truth assignments. $[A]$ means the set of all valuations, under which, the sentence in brackets evaluates to true. I think in the definition you are missing braces, it should be $[A] = \{ v \in M : v(A) = 1 \}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.