Prove DeMorgan's Laws for sets?
Let A, B, and C be sets. Then
A - (B union C) = (A - B) intersection (A - C) and A - (B intersection C) = (A - B) union (A - C)
Counting problems using lists?
1.) A U.S. Social Security number is a nine-digit number. The first digit(s) may be 0.
a.) How many SS numbers are available?
b.) How many of these are even?
c.) How many have all of their digits even?
d.) How many read the same backward and forward?
e.) How many have none of their digits equal to 8?
f.) How many have at least one digit equal to 8?
g.) How many have exactly one 8?
u is equal n koma b is equal p a is equal phie
To prove DeMorgan's Laws for sets:
1. A - (B union C) = (A - B) intersection (A - C):
To prove this, we need to show that an element is in the left-hand side if and only if it is in the right-hand side, and vice versa.
- If x is in A - (B union C), it means x is in A but not in (B union C). This implies that x is in A and x is not in either B or C. This can be written as x is in A and x is not in B, and x is in A and x is not in C. Therefore, x is in (A - B) and x is in (A - C). Hence, x is in (A - B) intersection (A - C).
- Conversely, if x is in (A - B) intersection (A - C), it means x is in both (A - B) and (A - C). This implies that x is in A but not in B, and x is in A but not in C. If x is not in B, then it is not in (B union C), and if x is not in C, then it is also not in (B union C). Thus, x is in A - (B union C).
Therefore, we have shown that A - (B union C) = (A - B) intersection (A - C).
2. A - (B intersection C) = (A - B) union (A - C):
Similarly, to prove this, we need to show that an element is in the left-hand side if and only if it is in the right-hand side, and vice versa.
- If x is in A - (B intersection C), it means x is in A but not in (B intersection C). This implies that x is in A and x is not in both B and C. This can be written as x is in A and x is not in B, or x is in A and x is not in C. Therefore, x is in (A - B) or x is in (A - C). Hence, x is in (A - B) union (A - C).
- Conversely, if x is in (A - B) union (A - C), it means x is in either (A - B) or (A - C). This implies that x is in A but not in B, or x is in A but not in C. If x is not in B, it is not in (B intersection C), and if x is not in C, it is also not in (B intersection C). Thus, x is in A - (B intersection C).
Therefore, we have shown that A - (B intersection C) = (A - B) union (A - C).
Now, let's move on to the counting problems using lists:
a.) How many SS numbers are available?
Since a U.S. Social Security number is a nine-digit number, the first digit can be any digit from 0 to 9 (including 0). For the remaining eight digits, each can be any digit from 0 to 9 (excluding the first digit). Therefore, the total number of available SS numbers is 10^8, which is 100,000,000.
b.) How many of these are even?
For a number to be even, the last digit must be an even digit. There are five even digits from 0 to 9: 0, 2, 4, 6, and 8. Therefore, there are 5 choices for the last digit, and for the remaining eight digits, each can be any digit from 0 to 9. So, the total number of SS numbers that are even is 5 * 10^8, which is 500,000,000.
c.) How many have all of their digits even?
For number to have all of its digits even, each of the nine digits must be an even digit. There are five even digits to choose from: 0, 2, 4, 6, and 8. Therefore, there are 5 choices for each of the nine digits. So, the total number of SS numbers with all even digits is 5^9, which is 195,3125.
d.) How many read the same backward and forward?
For a number to read the same backward and forward, it must be a palindrome. The first digit can be any digit from 0 to 9 (including 0). The second digit can also be any digit from 0 to 9. However, for the rest of the digits, they must match their corresponding positions from the front. Therefore, the total number of palindromic SS numbers is 10 * 10 * 10 = 1000.
e.) How many have none of their digits equal to 8?
Since there are nine positions for digits in the SS number, and there are nine possible digits from 0 to 9, including 0, we can choose any digit for each position. However, we need to exclude the digit 8. Therefore, the number of SS numbers where none of the digits are equal to 8 is 9^9, which is 387,420,489.
f.) How many have at least one digit equal to 8?
To calculate this, we can subtract the number of SS numbers with none of their digits equal to 8 from the total number of SS numbers available. So, the number of SS numbers with at least one digit equal to 8 is 10^8 - 9^9 = 99,612,579.
g.) How many have exactly one 8?
For number to have exactly one digit equal to 8, we need to choose one position out of the nine positions as the position for the digit 8. The other eight positions can be filled with any digit from 0 to 9 (excluding 8). Therefore, the number of SS numbers with exactly one digit equal to 8 is 9 * 9^8, which is 531,441.